Полный граф

• Полный граф с ${\displaystyle n}$ вершинами имеет ${\displaystyle n(n-1)/2}$ рёбер, это треугольное число.

• Полный граф с ${\displaystyle n}$ вершинами является регулярным графом степени ${\displaystyle n-1}$.

• Любой полный граф является своей максимальной кликой.

• Граф ${\displaystyle K_{n}}$ является ${\displaystyle (n-1)}$-связным.

• Дополнение графа ${\displaystyle K_{n}}$ — это пустой граф, то есть граф без рёбер.

• Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.

• В полном графе не может быть независимого множества более чем из одной вершины^[7].

• Пусть ${\displaystyle n\in \mathbb {N} }$, а ${\displaystyle \,T_{1},T_{2},\dots ,T_{n}}$ — семейство деревьев ограниченных степеней, где для любого ${\displaystyle i\in \{1,2,\dots n\}}$ число вершин дерева ${\displaystyle T_{i}}$ равно ${\displaystyle i}$. Тогда граф ${\displaystyle K_{n}}$ можно разложить на деревья ${\displaystyle \,T_{1},T_{2},\dots ,T_{n}}$, то есть существуют попарно рёберно-непересекающиеся копии графов ${\displaystyle \,T_{1},T_{2},\dots ,T_{n}}$ в графе ${\displaystyle K_{n}}$, и каждое ребро графа ${\displaystyle K_{n}}$ принадлежит хотя бы одной из этих копий^[8].

• Число различных путей между двумя выделенными вершинами в полном графе ${\displaystyle K_{n+2}}$ вычисляется^[9] по формуле ${\displaystyle w_{n+2}=n!e_{n}=\lfloor en!\rfloor }$, где через ${\displaystyle e}$ обозначена постоянная Эйлера, и

  ${\displaystyle e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.}$

• Индексы Хосойи (полные числа паросочетаний) полного графа являются телефонными числами (${\displaystyle n}$-ое телефонное число — это число различных вариантов, которыми из ${\displaystyle n}$ человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причём на полных графах реализуются максимально возможные значения индекса Хосойи для ${\displaystyle n}$-вершинного графа^[10]. Эти индексы образуют последовательность

  1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, … последовательность A000085 в OEIS.

• Число совершённых паросочетаний графа ${\displaystyle K_{n}}$ с чётным ${\displaystyle n}$ определяется с помощью двойного факториала и равняется ${\displaystyle (n-1)!!}$^[11].

• Теорема Рамсея: Для любых ${\displaystyle c}$ натуральных чисел ${\displaystyle n_{1},n_{2},\dots ,n_{c}}$ в любой ${\displaystyle c}$-цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с ${\displaystyle n_{i}}$ вершинами для некоторого цвета ${\displaystyle i}$. В частности, для любых ${\displaystyle r}$ и ${\displaystyle s}$, достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из ${\displaystyle r}$ вершин, либо полный белый подграф из ${\displaystyle s}$ вершин^[12].

• Теорема Турана: Обозначим через ${\displaystyle {\textrm {ex}}(v,n)}$ максимальное количество рёбер, которое может иметь граф с ${\displaystyle v}$ вершинами, не содержащий подграфа, изоморфного ${\displaystyle K_{n}}$. Тогда, если ${\displaystyle v=m(n-1)+r}$, где ${\displaystyle r}$ — остаток от деления ${\displaystyle v}$ на ${\displaystyle n-1}$, то этот максимум равен ${\displaystyle {\textrm {ex}}(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2}}.}$ Среди всех графов на ${\displaystyle v}$ вершинах, не содержащих подграфа ${\displaystyle K_{n}}$, этот максимум по количеству рёбер достигается на графе ${\displaystyle T_{n}(v)}$, определяемом следующим образом. Пусть ${\displaystyle T_{n}(v)}$ это граф с ${\displaystyle v}$ вершинами, разобьём все вершины на ${\displaystyle n-1}$ «почти равных» групп (то есть возьмём ${\displaystyle r}$ групп по ${\displaystyle m+1}$ вершине и ${\displaystyle n-1-r}$ групп по ${\displaystyle m}$ вершин, если ${\displaystyle v:(n-1)=m}$ с остатком ${\displaystyle r}$) и соединим рёбрами все пары вершин из разных групп. Таким образом получим ${\displaystyle (n-1)}$-дольный граф^[13].

• Теорема Кэли о числе деревьев: Число остовных деревьев в полном графе ${\displaystyle K_{n}}$ равно ${\displaystyle n^{n-2}}$^[14].

Известна верхняя оценка на число пересечений полного графа, а именно ${\displaystyle {\textrm {cr}}(K_{n})\leq {\tfrac {1}{4}}\left\lfloor {\tfrac {n}{2}}\right\rfloor \left\lfloor {\tfrac {n-1}{2}}\right\rfloor \left\lfloor {\tfrac {n-2}{2}}\right\rfloor \left\lfloor {\tfrac {n-3}{2}}\right\rfloor }$. Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл^[15], известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой — как «изображения Харари-Хилла»^[16]. Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердить^[17] оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно ${\displaystyle {\textrm {cr}}(K_{n})={\tfrac {1}{4}}\left\lfloor {\tfrac {n}{2}}\right\rfloor \left\lfloor {\tfrac {n-1}{2}}\right\rfloor \left\lfloor {\tfrac {n-2}{2}}\right\rfloor \left\lfloor {\tfrac {n-3}{2}}\right\rfloor }$. Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых ${\displaystyle n}$^[18]. Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работе^[19] за 1960 год содержатся прямые намёки на данный вопрос, или гипотезой Харари-Хилла, так как работа^[20] Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы^[21]. Полные графы ${\displaystyle K_{n}}$ при ${\displaystyle n\leq 4}$ являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал^[22], что гипотеза Хилла верна для всех ${\displaystyle n\leq 10}$, а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердили^[23] гипотезу Хилла для ${\displaystyle n=11,12}$. В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили^[24], что ${\displaystyle {\textrm {cr}}(K_{13})}$ является нечётным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

${\displaystyle G}$	${\displaystyle K_{5}}$	${\displaystyle K_{6}}$	${\displaystyle K_{7}}$	${\displaystyle K_{8}}$	${\displaystyle K_{9}}$	${\displaystyle K_{10}}$	${\displaystyle K_{11}}$	${\displaystyle K_{12}}$	${\displaystyle K_{13}}$
${\displaystyle {\textrm {cr}}(G)}$	${\displaystyle 1}$	${\displaystyle 3}$	${\displaystyle 9}$	${\displaystyle 18}$	${\displaystyle 36}$	${\displaystyle 60}$	${\displaystyle 100}$	${\displaystyle 150}$	${\displaystyle 219,221,223}$ или ${\displaystyle 225}$

Кроме того, в 1969 году Гай получил^[25] нижнюю оценку на число пересечений полного графа, а именно ${\displaystyle {\textrm {cr}}(K_{n})\geq {\tfrac {1}{120}}n(n-1)(n-2)(n-3)}$. При этом, ещё в 1960 году он обнаружил^[19], что существует предел ${\displaystyle \lim _{n\to \infty }{{\textrm {cr}}(K_{n})/Z(n)}}$, где ${\displaystyle Z(n)={\tfrac {1}{4}}\left\lfloor {\tfrac {n}{2}}\right\rfloor \left\lfloor {\tfrac {n-1}{2}}\right\rfloor \left\lfloor {\tfrac {n-2}{2}}\right\rfloor \left\lfloor {\tfrac {n-3}{2}}\right\rfloor }$, а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили^[26], что верна оценка

${\displaystyle \lim _{n\to \infty }{\frac {{\textrm {cr}}(K_{n})}{Z(n)}}\geq 0.8594}$.

Для ${\displaystyle n\leq 7}$ и ${\displaystyle n=9}$ число прямолинейных пересечений графа ${\displaystyle K_{n}}$, которое обычно обозначается через ${\displaystyle {\textrm {rcr}}(K_{n})}$, совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа ${\displaystyle K_{8}}$ равно ${\displaystyle 19}$, тогда как ${\displaystyle {\textrm {cr}}(K_{8})=18}$^[20]. В 2001 году Алекс Бродский, Стефан Дуроше и Эллен Гетнер выяснили^[27], что число прямолинейных пересечений графа ${\displaystyle K_{10}}$ равно 62, при ${\displaystyle {\textrm {cr}}(K_{10})=60}$. На данный момент точные значения ${\displaystyle {\textrm {rcr}}(K_{n})}$ известны для ${\displaystyle n\leq 27}$ и ${\displaystyle n=30}$. Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для ${\displaystyle n\leq 27}$ были построены^[28] совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для ${\displaystyle n=30}$ построена^[29] совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином Айххольцером^[30]. Кроме того, Айххольцер опубликовал^[30] на своём сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на ${\displaystyle {\textrm {rcr}}(K_{n})}$ вплоть до ${\displaystyle n=100}$. Ниже приведена таблица с соответствующими оценками для ${\displaystyle 5\leq n\leq 30}$.

${\displaystyle G}$

${\displaystyle K_{5}}$

${\displaystyle K_{6}}$

${\displaystyle K_{7}}$

${\displaystyle K_{8}}$

${\displaystyle K_{9}}$

${\displaystyle K_{10}}$

${\displaystyle K_{11}}$

${\displaystyle K_{12}}$

${\displaystyle K_{13}}$

${\displaystyle K_{14}}$

${\displaystyle K_{15}}$

${\displaystyle K_{16}}$

${\displaystyle K_{17}}$

${\displaystyle K_{18}}$

${\displaystyle K_{19}}$

${\displaystyle K_{20}}$

${\displaystyle K_{21}}$

${\displaystyle K_{22}}$

${\displaystyle K_{23}}$

${\displaystyle K_{24}}$

${\displaystyle K_{25}}$

${\displaystyle K_{26}}$

${\displaystyle K_{27}}$

${\displaystyle K_{28}}$

${\displaystyle K_{29}}$

${\displaystyle K_{30}}$

${\displaystyle {\textrm {rcr}}(G)}$

${\displaystyle 1}$

${\displaystyle 3}$

${\displaystyle 9}$

${\displaystyle 19}$

${\displaystyle 36}$

${\displaystyle 62}$

${\displaystyle 102}$

${\displaystyle 153}$

${\displaystyle 229}$

${\displaystyle 324}$

${\displaystyle 447}$

${\displaystyle 603}$

${\displaystyle 798}$

${\displaystyle 1029}$

${\displaystyle 1318}$

${\displaystyle 1657}$

${\displaystyle 2055}$

${\displaystyle 2528}$

${\displaystyle 3077}$

${\displaystyle 3699}$

${\displaystyle 4430}$

${\displaystyle 5250}$

${\displaystyle 6180}$

${\displaystyle 7233}$ или ${\displaystyle 7234}$

${\displaystyle 8421}$, ${\displaystyle 8422}$ или ${\displaystyle 8423}$

${\displaystyle 9726}$

В 1994 году Эдвард Р. Шайнерман и Герберт С. Уилф обнаружили^[31] неожиданную связь между числом прямолинейных пересечений графа ${\displaystyle K_{n}}$ и задачей Сильвестра «о четырёх точках» из вероятностной геометрии^[32]. Пусть ${\displaystyle R}$ — открытое множество на плоскости с конечной мерой Лебега. Обозначим через ${\displaystyle {\textrm {q}}(R)}$ вероятность того, что если в ${\displaystyle R}$ равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырёхугольником, а через ${\displaystyle {\textrm {q}}^{*}}$ — инфимум значений ${\displaystyle {\textrm {q}}(R)}$ по всем таким ${\displaystyle R}$. Тогда верно равенство

${\displaystyle \lim _{n\to \infty }{\frac {{\textrm {rcr}}(K_{n})}{n \choose 4}}={\textrm {q}}^{*},}$

где ${\displaystyle {n \choose 4}}$ обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялись^[33] верхняя и нижняя оценки на константу ${\displaystyle {\textrm {q}}^{*}}$, и на данный момент лучшая нижняя^[34] и лучшая верхняя^[28] оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

${\displaystyle 0.379972<{\frac {277}{729}}\leq {\textrm {q}}^{*}\leq {\frac {83247328}{218791125}}<0.380488.}$

Графы с ${\displaystyle K_{1}}$ по ${\displaystyle K_{4}}$ являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф ${\displaystyle K_{5}}$ и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского^[35].

При ${\displaystyle n\leq 6}$ граф ${\displaystyle K_{n}}$ является 1-планарным графом, но при ${\displaystyle n\geq 7}$ граф ${\displaystyle K_{n}}$ не является 1-планарным^[36].

Книжная толщина графа ${\displaystyle K_{5}}$ равна ${\displaystyle 3}$. Для любых ${\displaystyle n\geq 4}$ граф ${\displaystyle K_{n}}$ имеет книжную толщину в точности ${\displaystyle \lceil n/2\rceil }$^[37].

Полный граф образуется из вершин и рёбер (n-1)-симплекса. Так, например, геометрически ${\displaystyle K_{3}}$ образует множество вершин и рёбер треугольника, ${\displaystyle K_{4}}$ — тетраэдра и так далее. Объединение всех семи вершин и двадцати одного рёбра многогранника Часара, топологически эквивалентного тору, образует полный граф ${\displaystyle K_{7}}$.

Граф 2-смежностного многогранника является полным графом.

Граф ${\displaystyle K_{6}}$ не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Кэмерон Гордон в 1983 году, для любого вложения ${\displaystyle K_{6}}$ в трёхмерное пространство существует два таких цикла в ${\displaystyle K_{6}}$, образы которых при вложении имеют нечётный коэффициент зацепления^[38]. А для любого вложения графа ${\displaystyle K_{7}}$ в трёхмерное пространство существует такой гамильтонов цикл в ${\displaystyle K_{7}}$, образ которого при вложении имеет нетривиальный инвариант Арфа, то есть является нетривиальным узлом^[38]. В 2002 году Эрика Флапан доказала, что для любого ${\displaystyle m\in \mathbb {N} }$ найдётся такое ${\displaystyle n\in \mathbb {N} }$, что каждое вложение графа ${\displaystyle K_{n}}$ в ${\displaystyle \mathbb {R} ^{3}}$ содержит двукомпонентое зацепление, коэффициент зацепления которого равен ${\displaystyle m}$.^[39] А кроме того, для любого ${\displaystyle m\in \mathbb {N} }$ найдётся такое ${\displaystyle r\in \mathbb {N} }$, что каждое вложение графа ${\displaystyle K_{n}}$ в ${\displaystyle \mathbb {R} ^{3}}$ содержит узел ${\displaystyle Q}$, такой что ${\displaystyle |a_{2}(Q)|\geq m}$, где через ${\displaystyle a_{2}(Q)}$ обозначен второй коэффициент многочлена Конвея узла ${\displaystyle Q}$.^[39]

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

K1 (0)	K2 (1)	K3 (3)	K4 (6)	K5 (10)	K6 (15)
K7 (21)	K8 (28)	K9 (36)	K10 (45)	K11 (55)	K12 (66)