Полный граф - простой граф, в котором каждая пара различных вершин смежная, т.е. существует ребро, соединяющее эти вершины. Полный граф обычно обозначается K _n.

Свойства

• Полный граф с n вершинами имеет n (n - 1) / 2 ребер
• Полный граф с n вершинами есть регулярным графом степени n - 1.
• Графы K ₁ - K ₄ является планарными. Полные графы с большим количеством вершин не является планарными, поскольку содержат подграф K ₅ и, следовательно, не удовлетворяют условия Куратовского.

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

Источники

• Ф. Харари. Теория графов. М.: "Мир". 1973
• Р.Уилсон. Введение в теорию графов. М.: Мир, 1977