Граф Пуссена — это планарный граф с 15 вершинами и 39 рёбрами. Он назван именем Шарля Жана де Ла Валле-Пуссена.
История В 1879 году опубликовал доказательство теоремы о четырёх красках, одной из великих гипотез в теории графов. Хотя сама теорема верна, доказательство Кемпе ошибочно. Перси Джон Хивуд продемонстрировал это в 1890 контрпримером, а де Ла Валле-Пуссен пришёл к тому же заключению в 1896 году с графом Пуссена.
(Неверное) доказательство Кемпе основано на и, поскольку это доказательство на основе цепей оказалось полезным в теории графов, математики продолжают интересоваться такими контрпримерами. Другие контрпримеры были найдены позже, это граф Эрреры в 1921, граф Киттелля в 1935 с 23 вершинами и, наконец, два минимальных контрпримера (граф Сойфера в 1997 и в 1998, оба порядка 9).
Другие свойства Кликовая ширина графа равна 7.
Примечания
Литература
Ссылки Eric W. Weisstein, Poussin Graph (MathWorld)
Категория:Графы, имеющие собственные названия