Полный граф

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

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

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