Полный граф

Полный граф
Вершины	n
Рёбра	$\frac{n (n-1)}{2}$
Диаметр	1
Автоморфизм	n! (Sn)
Хроматическое число	n
Хроматический индекс	n если n - нечётное, иначе n − 1
Обозначение	Kn

Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с $n$ вершинами имеет $n(n-1)/2$ рёбер и обозначается $K_n$. Является регулярным графом степени $n-1$.

Графы с $K_1$ по $K_4$ являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф $K_5$ и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Примеры

Ниже приведены полные графы с числом вершин от 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