Граф Петерсена — неорієнтований граф з 10 вершинами і 15 ребрами. Це невеличкий граф, який слугує корисним прикладом або контрприкладом для багатьох проблем в теорії графів. Названий на честь Юліуса Петерсена, який у 1898 побудував його як найменший безмостовийкубічний граф з неможливістю триколірного розфарбування ребер.[1] Хоча граф звичайно приписують Петерсену, він з'явився на 12 років раніше, в 1886.[2]
Дональд Кнут стверджує, що граф Петерсена це «видатна форма, що слугує контрприкладом для багатьох оптимістичних пророцтв про те, що може бути правильним для графів загалом.»[3]
Граф Петерсена — це доповненняреберного графа для . Це також граф Кнесера; це значить, що він має по одній вершині для кожного 2-елементної підмножини 5-елементної множини, і дві вершини зв'язані ребром тоді і тільки тоді, якщо відповідні двохелементні підмножини не перетинаються між собою. Як граф Кнесера форми — це приклад непарного графа.
Геометрично, граф Петерсена є графом, утвореним вершинами і ребрами напівдодекаедра, тобто додекаедра з ототожненими протилежними вершинами, ребрами і гранями.
Найпоширеніший малюнок графа Петерсена, пентаграма всередині пентагона, має п'ять перетинів. Однак, це найкращий малюнок з огляду на кількість перетинів; існує інше зображення лише з двома перетинами. На торі граф Петерсена можна намалювати без перетинів; отже його зорієнтований рід 1.
↑Kempe, A. B. (1886), A memoir on the theory of mathematical form, Philosophical Transactions of the Royal Society of London, 177: 1—70, doi:10.1098/rstl.1886.0002
↑Knuth, Donald E., The Art of Computer Programming; volume 4, pre-fascicle 0A. A draft of section 7: Introduction to combinatorial searching