Повний граф

Повний граф — простий граф, в якому кожна пара різних вершин суміжна, тобто існує ребро, що сполучає ці вершини. Повний граф зазвичай позначається K_n.

Властивості

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

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

$K_1:0$	$K_2:1$	$K_3:3$	$K_4:6$
$K_5:10$	$K_6:15$	$K_7:21$	$K_8:28$
$K_9:36$	$K_{10}:45$	$K_{11}:55$

Див. також

• Напівікосаедр
• Універсальний граф

Джерела

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