Граф дружеских отношений
Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами[1].
Граф дружеских отношений Fn можно построить путём соединения n копий цикла C3 в одной общей вершинеШаблон:Sfn.
По построению граф дружеских отношений Fn изоморфен мельнице Wd(3,n). Граф является графом единичных расстояний, имеет обхват 3, диаметр 2 и радиус 1. Граф F2 изоморфен бабочке.
Теорема о графе дружеских отношений
Теорема о графе дружеских отношений Эрдёша, Реньи и Веры СосШаблон:SfnШаблон:Sfn утверждает, что конечные графы со свойством, что любые две вершины имеют в точности одного общего соседа, это в точности графы дружеских отношений. Неформально, если группа людей обладает свойством, что любая пара людей имеет в точности одного общего друга, то должно быть одно лицо, являющееся другом остальных членов группы. Для бесконечных графов, однако, может существовать много различных графов одной и той же мощности, имеющих это свойствоШаблон:Sfn.
Комбинаторное доказательство теоремы о графе дружеских отношений дали Мертциос и УнгерШаблон:Sfn. Другое доказательство дал Крейг ХунекеШаблон:Sfn.
Разметка и раскраска
Граф дружеских отношений имеет хроматическое число 3 и хроматический индекс 2n. Его хроматический многочлен может быть получен из хроматического многочлена цикла C3 и равен .
Граф дружеских отношений Fn имеет совершенную разметку рёбер тогда и только тогда, когда n нечётно. Он имеет грациозную разметку тогда и только тогда, когда n ≡ 0 (mod 4), или n ≡ 1 (mod 4)Шаблон:SfnШаблон:Sfn.
Любой граф дружеских отношений является фактор-критическим.
Экстремальная теория графов
Согласно экстремальной теории графов любой граф с достаточно большим числом рёбер (по отношению к числу вершин) должен содержать k-лопастной вентилятор в качестве подграфа. Более точно, это верно для графа с n вершинами, если число рёбер равно
где f(k) равно k2 − k, если k нечётно, и f(k) равно k2 − 3k/2, если k чётно. Эти границы обобщают теорему Турана о числе рёбер в графе без треугольников и они являются лучшими границами для данной задачи, поскольку для любого меньшего числа рёбер существуют графы, не содержащие k-лопастного вентилятораШаблон:Sfn.