Полный граф

Полный граф
K7, полный граф с 7 вершинами
Вершин	n
Рёбер	${\displaystyle {\frac {n(n-1)}{2}}}$
Диаметр	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{иначе}}\end{array}}\right.}$
Обхват	${\displaystyle \left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{иначе}}\end{array}}\right.}$
Автоморфизмы	n! (Sn)
Хроматическое число	n
Хроматический индекс	n если n - нечётное, иначе n − 1
Спектр	${\displaystyle \left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{иначе}}\end{array}}\right.}$
Свойства	(n − 1)-регулярный граф Симметричный граф Вершинно-транзитивный граф Рёберно-транзитивный граф Сильно регулярный граф Целый граф Гамильтонов граф
Обозначение	Kn
Медиафайлы на Викискладе

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.^[1] По́лный ориенти́рованный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями.^[2] Принято считать, что теория графов берет свое начало с решения Леонардом Эйлером задачи о семи кёнигсбергских мостах, датированного 1736 годом, однако изображения полных графов, вершины которых располагаются в вершинах правильных многоугольников, встречаются ещё в 13 веке, в работе Раймунда Луллия.^[3] Подобные рисунки иногда называют мистическими розами.^[4]

Обычно полный граф с ${\displaystyle n}$ вершинами обозначается через ${\displaystyle K_{n}}$. Некоторые источники утверждают, что буква ${\displaystyle K}$ в этом обозначении является сокращением от немецкого слова нем. komplett,^[5] в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, нем. vollständiger Graph, не содержит буквы ${\displaystyle K}$. По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.^[6]

• Полный граф с ${\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)

• Карпов Д. В. Теория графов (рус.) — М.: МЦНМО, 2022. — 560 с. — ISBN 978-5-4439-1690-3.
• Ábrego B. M., Fernández-Merchant S., Salazar G. The rectilinear crossing number of ${\displaystyle K_{n}}$: Closing in (or Are We?) (англ.) // Thirty essays on geometric graph theory / János Pach|en. — N. Y.: Springer, 2013. — P. 5-18. — doi:10.1007/978-1-4614-0110-0_2.
• Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. 3-symmetric and 3-decomposable geometric drawings of ${\displaystyle K_{n}}$ (англ.) // Discrete Applied Mathematics^[англ.]. — 2010. — Vol. 158, iss. 12. — P. 1240-1258. — doi:10.1016/j.dam.2009.09.020.
• Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of ${\displaystyle K_{n}}$ (англ.) // Discrete & Computational Geometry^[англ.]. — 2012. — Vol. 48, iss. 1. — P. 192-215. — doi:10.1007/s00454-012-9403-y.
• Aichholzer O. On the Rectilinear Crossing Number (англ.) (26 мая 2015). Дата обращения: 22 января 2023.
• Bang-Jensen J., Gutin G.^[англ.]. Classes of Directed Graphs (англ.) — Springer International Publishing, 2018. — 560 p. — (Springer Monographs in Mathematics). — doi:10.1007/978-3-319-71840-8_1.
• Beineke L. W.^[англ.], Wilson R.^[англ.]. The early history of the brick factory problem (англ.) // The Mathematical Intelligencer^[англ.]. — 2010. — Vol. 32, iss. 2. — P. 41-48. — doi:10.1007/s00283-009-9120-4.
• Bernhart F. R., Kainen P. C.^[англ.]. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2.
• Blažek J., Koman M. A minimal problem concerning complete plane graphs (англ.) // Miroslav Fiedler^[англ.] Theory of graphs and its applications. — Czech Academy of Sciences, 1964. — P. 113-117.
• Brodsky A., Durocher S., Gethner E.^[англ.]. The rectilinear crossing number of ${\displaystyle K_{10}}$ is 62 (англ.) // The Electronic Journal of Combinatorics^[англ.]. — 2001. — Vol. 8, iss. 1. — P. 1-30.
• Callan D. A combinatorial survey of identities for the double factorial (англ.). — 2009. — Bibcode: 2009arXiv0906.1317C. — arXiv:0906.1317.
• Cetina M., Hernández-Vélez C., Leaños J., Guillén C. V. Point sets that minimize (≤k)-edges, 3-decomposable drawings, and the rectilinear crossing number of ${\displaystyle K_{30}}$ (англ.) // Discrete Mathematics. — 2012. — Vol. 311, iss. 16. — P. 1646–1657. — doi:10.1016/j.disc.2011.03.030.
• Conway J. H., Gordon C. McA^[англ.]. Knots and links in spatial graphs (англ.) // Journal of Graph Theory. — 1983. — Vol. 7, no. 4. — P. 445-453. — doi:10.1002/jgt.3190070410.
• Erica Flapan^[англ.]. Intrinsic knotting and linking of complete graphs (англ.) // Algebraic & Geometric Topology^[англ.]. — 2002. — Vol. 2, no. 1. — P. 371-380. — doi:10.2140/agt.2002.2.371.
• Gries D., Schneider F. B. A Logical Approach to Discrete Math (англ.) — B.: Springer, 1993. — 436 p. — ISBN 978-0387941158.
• Guy R. K. A combinatorial problem (англ.) // NABLA (Bulletin of the Malaysian Mathematical Sciences Society). — 1960. — Vol. 7. — P. 68-72.
• Guy R. K. The decline and fall of Zarankiewicz’s theorem (англ.) // Frank Harary Proof Techniques in Graph Theory. — N. Y.: Academic Press, 1969. — P. 63–69.
• Guy R. K. Crossing numbers of graphs (англ.) // Graph Theory and Applications. — Berlin, Heidelberg: Springer, 1972. — P. 111-124.
• Harary F., Hill A. On the number of crossings in a complete graph (англ.) // Proceedings of the Edinburgh Mathematical Society. — Edinburgh, 1963. — Vol. 13, iss. 4. — P. 333-338.
• Hassani M. Cycles in graphs and derangements (англ.) // The Mathematical Gazette^[англ.]. — 2004. — Vol. 88, iss. 511. — P. 123-126. — doi:10.1017/S0025557200174443.
• Joos F., Kim J., Kuhn D., Osthus D. Optimal packings of bounded degree trees (англ.) // Journal of the European Mathematical Society. — 2019. — 8 May (vol. 21, iss. 12). — P. 3573-3647. — ISSN 1435-9855. — doi:10.4171/JEMS/909.
• de Klerk E., Pasechnik D. V., Schrijver A. Reduction of symmetric semidefinite programs using the regular ∗-representation (англ.) // Mathematical Programming^[англ.]. — 2007. — Vol. 109, iss. 2-3, Ser. B. — P. 613-624. — doi:10.1007/s10107-006-0039-7.
• Knuth D. E. Two thousand years of combinatorics // Combinatorics: Ancient & Modern (англ.) / Robin Wilson^[англ.], John J. Watkins. — Oxf.: Oxford University Press, 2015. — P. 7–37. — 392 p. — ISBN 978-0191630620.
• McQuillan D., Pan S., Richter R. B. On the crossing number of ${\displaystyle K_{13}}$ (англ.) // Journal of Combinatorial Theory, Series B. — 2015. — Vol. 115. — P. 224–235. — doi:10.1016/j.jctb.2015.06.002.
• Pirnot T. L. Mathematics All Around (англ.) — Boston: Addison Wesley, 2000. — 814 p. — ISBN 978-0201308150.
• Pan S., Richter B. R. The crossing number of ${\displaystyle K_{11}}$ is 100 (англ.) // Journal of Graph Theory. — 2007. — Vol. 56, iss. 2. — P. 128-134. — doi:10.1002/jgt.20249.
• Ramsey F. P. On a problem of formal logic (англ.) // Proceedings of the London Mathematical Society. — L., 1930. — Vol. 30. — P. 264—286. — doi:10.1112/plms/s2-30.1.264.
• Schaefer M. Crossing numbers of graphs (англ.) — Boca Raton: CRC Press, 2018. — 376 p. — doi:10.1201/9781315152394.
• Scheinerman E. R.^[англ.], Wilf H. S.^[англ.]. The rectilinear crossing number of a complete graph and Sylvester's “four point problem” of geometric probability (англ.) // The American mathematical monthly^[англ.]. — 1994. — Vol. 101, iss. 10. — P. 939-943. — doi:10.2307/2975158.
• Tichy R. F., Wagner S. Extremal problems for topological indices in combinatorial chemistry (англ.) // Journal of Computational Biology^[англ.]. — 2005. — Vol. 12, iss. 7. — P. 1004–1013. — doi:10.1089/cmb.2005.12.1004. — PMID 16201918.
• Weisstein E. W. Sylvester's Four-Point Problem (англ.) (2004). Дата обращения: 24 января 2023.