Полный граф

Полный граф
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 K_{9}}$ на рисунке из труда Ars Magna Раймунда Луллия.

Обычно полный граф с ${\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_{5}}$

Планарность и книжная толщина

Графы с ${\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]

Симплексы и многогранники

Интерактивное изображение многогранника Часара. Водите мышью влево и вправо чтобы поворачивать SVG изображение.

Полный граф образуется из вершин и ребер (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)

Примечания

1. Карпов Дмитрий Валерьевич, 2022, p. 17.
2. Bang-Jensen, Gutin, 2018, p. 17.
3. Donald E. Knuth, 2015.
4. Mystic Rose (англ.). nrich.maths.org. Дата обращения: 22 января 2023.
5. Gries, Schneider, 1993.
6. Thomas L. Pirnot, 2000, p. 154.
7. Карпов Дмитрий Валерьевич, 2022, p. 374.
8. Joos, Kim, Kuhn, Osthus, 2019.
9. Mehdi Hassani, 2004.
10. Tichy, Wagner, 2005.
11. David Callan, 2009.
12. Frank P. Ramsey, 1930.
13. Карпов Дмитрий Валерьевич, 2022, p. 494.
14. Карпов Дмитрий Валерьевич, 2022, p. 424.
15. Beineke, Wilson, 2010, p. 43.
16. Marcus Schaefer, 2018.
17. Blažek, Koman, 1964.
18. Marcus Schaefer, 2018, p. 25.
19. Richard K. Guy, 1960.
20. Harary, Hill, 1963.
21. Marcus Schaefer, 2018, 1.3 Hill and the Crossing Number of Complete Graphs, p. 25: «the first explicit statement in print seems to be in a paper by Harary and Hill».
22. Richard K. Guy, 1972.
23. Pan, Richter, 2007.
24. McQuillan, Pan, Richter, 2015.
25. Richard K. Guy, 1969.
26. Klerk, Pasechnik, Schrijver, 2007.
27. Brodsky, Durocher, Gethner, 2001.
28. Ábrego, Fernández-Merchant, Leaños, Salazar, 2012.
29. Cetina, Hernández-Vélez, Leaños, Villalobos, 2012.
30. Aichholzer, 2015.
31. Scheinerman, Wilf, 1994.
32. Eric W. Weisstein, 2004, О задаче Сильвестра.
33. Ábrego, Fernández-Merchant, Salazar, 2013, История исследований числа прямолинейных пересечений полных графов..
34. Ábrego, Fernández-Merchant, Leaños, Salazar, 2010.
35. Карпов Дмитрий Валерьевич, 2022, p. 237.
36. Карпов Дмитрий Валерьевич, 2022, p. 308.
37. Kainen Bernhart, 1979, pp. 320–331.
38. Conway, Gordon, 1983.
39. Flapan, 2002.

Литература

• Карпов Д. В. Теория графов (рус.) — М.: МЦНМО, 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. — New York: 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 (англ.) — Berlin: 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. — New York: 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. — Oxford: 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. — London, 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.