Зада́ча Ко́нвея про 99-верши́нний граф — нерозв'язана задача, в якій запитується, чи існує неорієнтований граф з 99 вершинами, у якому кожні дві суміжні вершини мають рівно одного спільного сусіда і в якому дві несуміжні вершини мають рівно два спільних сусіди. Еквівалентно, будь-яке ребро має бути частиною єдиного трикутника, а будь-яка пара несуміжних вершин має бути на діагоналі єдиного 4-циклу. Джон Гортон Конвей оголосив про приз у 1000 доларів тому, хто розв'яже цю задачу.

Властивості Якщо такий граф існує, він буде локально лінійним сильно регулярним графом з параметрами (99,14,1,2). Перший, третій і четвертий параметри кодують твердження задачі — граф повинен мати 99 вершин, кожна пара суміжних вершин повинна мати 1 спільного сусіда, а будь-які несуміжні вершини повинні мати 2 спільних сусіди. Другий параметр означає, що граф є регулярним графом із 14 ребрами на вершину.

Якщо цей граф існує, він не має будь-яких симетрій порядку 11, звідки випливає, що його симетрії не можуть перевести будь-яку вершину в іншу вершину. Відомі й інші обмеження на можливі групи симетрій.

Історія Можливість існування графа з такими параметрами припускав вже 1969 року , а як відкриту задачу існування серед інших поставив Конвей. Конвей сам працював над цією задачою від 1975, але 2014 року оголосив приз тому, хто розв'яже задачу, як частину набору задач, представлених на конференції DIMACS з найважливіших проблем ідентифікації цілочисельних послідовностей. Цей набір задач також включає гіпотезу про трекл, найменшу відстань множин Данцера і питання, хто виграє після ходу 16 у грі в .

Пов'язані графи Загальніше, існує тільки п'ять можливих комбінацій параметрів, для яких сильно регулярний граф може існувати зі властивістю, що кожне ребро належить єдиному трикутнику, а кожне неребро (відсутнє ребро двох несуміжних вершин) утворює діагональ єдиного чотирикутника. Відомо лише, що графи існують із двома з п'яти цих комбінацій. Цими двома графами є граф Пелі з дев'ятьма вершинами (граф 3-3 дуопризми) з параметрами (9,4,1,2) та граф Берлекемпа — ван Лінта — Зейделя з параметрами (243,22,1,2). Задача про 99-вершинний граф запитує про найменшу із цих п'яти комбінацій параметрів, для яких існування графа невідоме.

Примітки