Граф дружеских отношений

Теорема о графе дружеских отношений Эрдёша, Реньи и Веры Сос[3][4] утверждает, что конечные графы со свойством, что любые две вершины имеют в точности одного общего соседа, это в точности графы дружеских отношений. Неформально, если группа людей обладает свойством, что любая пара людей имеет в точности одного общего друга, то должно быть одно лицо, являющееся другом остальных членов группы. Для бесконечных графов, однако, может существовать много различных графов одной и той же мощности, имеющих это свойство[5].

Комбинаторное доказательство теоремы о графе дружеских отношений дали Мертциос и Унгер[6]. Другое доказательство дал Крейг Хунеке[7].

Граф дружеских отношений имеет хроматическое число 3 и хроматический индекс 2n. Его хроматический многочлен может быть получен из хроматического многочлена цикла C₃ и равен ${\displaystyle (x-2)^{n}(x-1)^{n}x}$.

Граф дружеских отношений F_n имеет совершенную разметку рёбер тогда и только тогда, когда n нечётно. Он имеет грациозную разметку тогда и только тогда, когда n ≡ 0 (mod 4), или n ≡ 1 (mod 4)[8][9].

Любой граф дружеских отношений является фактор-критическим.

Согласно экстремальной теории графов любой граф с достаточно большим числом рёбер (по отношению к числу вершин) должен содержать k-лопастной вентилятор в качестве подграфа. Более точно, это верно для графа с n вершинами, если число рёбер равно

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

где f(k) равно k² − k, если k нечётно, и f(k) равно k² − 3k/2, если k чётно. Эти границы обобщают теорему Турана о числе рёбер в графе без треугольников и они являются лучшими границами для данной задачи, поскольку для любого меньшего числа рёбер существуют графы, не содержащие k-лопастного вентилятора[10].