Гипотеза о трекле
Граф – это набор точек (узлов), соединенных линиями (ребрами). Если граф рисуют на плоскости, ребра часто пересекаются между собой. В 1972 г. Джон Конвей определил трекл как граф, нарисованный на плоскости, у которого любые два ребра либо встречаются в узле и больше не пересекаются, либо не встречаются в узле, но при этом пересекаются ровно один раз. Говорят, что идею названия подал автору один шотландский рыболов, постоянно жаловавшийся на то, что у него запуталась (thrackled) леска.
На рисунке показаны два трекла. Левый имеет в своем составе 5 узлов и 5 ребер, тогда как правый – 6 узлов и 6 ребер. Конвей предположил, что у любого трекла число ребер меньше или равно числу узлов. Он предложил бутылку пива в награду тому, кто сможет это доказать или опровергнуть, но с годами, поскольку решение не появлялось, приз вырос до тысячи долларов.
Оба приведенных трекла представляют собой замкнутые петли (их узлы располагаются на кольцевом маршруте), нарисованные с наложением. Известно, что любая замкнутая петля с n³ 5 узлов может быть нарисована так, что образует трекл. Если это правда, то число E ребер может быть равно числу n узлов при любом n³ 5. Пал Эрдёш доказал, что гипотеза о трекле верна для любого графа с прямыми ребрами. Наилучшее на данный момент ограничение на размер E доказали Радослав Фулек и Янош Пач в 2011 г.:
Ссылку на дополнительную информацию см. в главе «Загадки разгаданные».