Снарк в теорії графів — це зв'язний кубічний граф без мостів з хроматичним індексом 4. Іншими словами, це граф з надмірною зв'язністю — усунення будь-якого ребра не призведе до розбиття графу, також кожна вершина має три сусідні вершини і ребра не можна розфарбувати тільки в три кольори, так щоб два ребра одного кольору не сходилися в одній вершині. (З теореми Візінга хроматичний індекс кубічного графу дорівнює 3 або 4.) Щоб уникнути тривіальних випадків, до снарків не відносять графи, які мають обхват менше 5.

Вважається, що незважаючи на просте визначення і тривалу історію вивчення, властивості і структура снарка маловідомі.

При вивченні різних важливих і складних проблем теорії графів (таких, як гіпотеза про подвійне покриття циклами[en] і гіпотеза про 5-потік) трапляються цікаві, але в чомусь дивні графи, які називаються снарками. Всупереч своїй простому визначенню … і більш ніж віковому вивченню, їх властивості та структура здебільшого залишаються невідомими.[1] Оригінальний текст (англ.) In the study of various important and difficult problems in graph theory (such as the Cycle double cover conjecture and the 5-Flow Conjecture), one encounters an interesting but somewhat mysterious variety of graphs called snarks. In spite of their simple definition...and over a century long investigation, their properties and structure are largely unknown.

Пітер Тет вперше зацікавився снарками в 1880 році, коли він довів, що теорема про чотири фарби еквівалентна твердженням, що ніякий снарк не є планарним^[2]. Першим відомим снарком став граф Петерсена, знайдений в 1898 році. У 1946 році югославський математик Данило Блануша^[en] знайшов ще два снарки, обидва з 18 вершинами, що отримали назву Снарк Блануші^[3]. Четвертого снарка знайшов двома роками пізніше Татт, який працював під псевдонімом Бланш Декарт (Blanche Descartes), і це був граф порядку 210^[4][5] У 1973 році Дьйордь Секереш знайшов п'ятий снарк — Снарк Секереша.^[6] У 1975 році Айзекс Руфус^[en] узагальнив метод Блануші для побудови двох нескінченних родин снарків — квіти і BDS (снарк Блануші — Декарта — Секереша), сімейство, що включає два снарки Блануші, снарк Декарта і снарк Секереша^[7]. Айзекс виявив також снарк з 30 вершинами, що не належить сімейству BDS і не є квіткою — подвійну зірку.

Термін «снарк» увів Мартін Гарднер 1976 року за назвою невловимої істоти «Снарк» з поеми «Полювання на Снарка» Льюїса Керролла^[8].

Всі снарки є негамільтоновими і більшість з відомих снарків є гіпогамільтоновими^[en] — видалення будь-якої окремої вершини дає гамильтонов підграф. Гіпогамільтонові снарки повинні бути бікритичними — видалення будь-яких двох вершин дає підграф, розфарбовуваний реберно в 3 кольори.^[9][10]

Було показано, що число снарків для заданого числа вершин обмежена експоненційної функцією^[11]. (Будучи кубічними графами, всі снарки повинні мати парне число вершин.) OEIS послідовність A130315 містить число нетривіальних снарків з 2n вершинами для малих значень n^[12].

Гіпотеза про подвійне покриття циклами^[en] стверджує, що в будь-якому графі без мостів можна знайти набір циклів, що покривають кожне ребро двічі, або, що еквівалентно, що граф можна вкласти в поверхню таким чином, що всі грані будуть простими циклами. Снарки утворюють важкий випадок для цієї гіпотези — якщо вона правильна для снарків, вона правильна для всіх графів^[13]. У зв'язку з цим Бранко Ґрюнбаум висловив гіпотезу, що не можна вкласти будь-який снарк в поверхню таким способом, що всі грані є простими циклами і при цьому дві будь-яких межі або не мають спільних ребер, або мають одне спільне ребро. Однак Мартін Кохол знайшов контрприклад до цієї гіпотези Ґрюнбаум^[14][15][16].

Татт висловив гіпотезу, що будь-який снарк має граф Петерсена як мінор. Таким чином, він припустив, що найменший снарк, граф Петерсена, можна отримати з будь-якого іншого снарка шляхом стягування деяких ребер і видалення інших. Що еквівалентно (оскільки граф Петерсена має максимальний степінь три) твердженню, що будь-який снарк містить підграф, який можна отримати з графу Петерсена шляхом ділення деяких ребер. Ця гіпотеза є посиленням теореми про чотири фарби, оскільки будь-який граф, що містить граф Петерсена як мінору, не може бути планарним. У 1999 році Робертсон^[en], Сандерс^[en], Сеймур^[en] і Томас^[en] оголосили про доведення гіпотези^[17], однак за станом на 2012 рік доведення так і не опубліковано^[18].

Татт також запропонував як гіпотезу узагальнену теорему про снарки для довільних графів — будь-який граф без мостів, що не має графу Петерсена як мінору, має ніде не нульовий 4-потік. Що означає, що ребрам графу можна задати напрямки і позначити числами з множини {1, 2, 3} так, що сума вхідних чисел мінус сума вихідних в кожній вершині ділиться на чотири. Як показав Татт, таке призначення для кубічних графів існує в тому і тільки в тому випадку, коли ребра можна розфарбувати в три кольори, так що в цьому випадку гіпотеза випливає з теореми про снарки. Однак гіпотеза залишається відкритою для інших графів (НЕ кубічних)^[19].

• Граф Петерсена (10 вершин, відкритий в 1898 році)
• Граф Тітце (12 вершин, але з обхватом 3, зазвичай не вважається снарком)
• Снарк Блануші (два снарки з 18 вершинами, відкриті в 1946 році)
• Снарк Декарта (210 вершин, відкритий пізніше Тату [en] в 1948 році)
• Снарк «Подвійна зірка» (30 вершин)
• Снарк Секереша (50 вершин, відкритий в 1973 році)
• Снарк Уоткінса (50 вершин, відкритий в 1989)
• Снарк «Квітка» (нескінченне сімейство з 20, 28, 36, 44 … вершинами, відкрито в 1975 році)

Список всіх снарків з 36 вершинами, за винятком снарка з 36 вершинами і обхватом 4, був створений Гуннаром Брінкманном, Яном Гедгебером, Джонасом Хегглундом і Класом Маркстремом в 2012 році^[20].

• Weisstein, Eric W. Snark(англ.) на сайті Wolfram MathWorld.
• Alen Orbanić, Tomaž Pisanski, Milan Randić, and Brigite Servatius (preprint). «Blanuša Double». Institute for Mathematics, Physics and Mechanics in Ljubljana, Slovenia.

Ця стаття має кілька недоліків. Будь ласка, допоможіть удосконалити її або обговоріть ці проблеми на сторінці обговорення. checktranslate Ця стаття містить текст, що не відповідає енциклопедичному стилю. Будь ласка, допоможіть удосконалити цю статтю, погодивши стиль викладу зі стилістичними правилами Вікіпедії. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (квітень 2016)