Повний граф

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

Властивості

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

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

${\displaystyle K_{1}:0}$	${\displaystyle K_{2}:1}$	${\displaystyle K_{3}:3}$	${\displaystyle K_{4}:6}$
${\displaystyle K_{5}:10}$	${\displaystyle K_{6}:15}$	${\displaystyle K_{7}:21}$	${\displaystyle K_{8}:28}$
${\displaystyle K_{9}:36}$	${\displaystyle K_{10}:45}$	${\displaystyle K_{11}:55}$

Див. також

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

Джерела

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

1. Thomas Fowler. Unique Coloring of Planar Graphs. — Georgia Institute of Technology Mathematics Department, 1998. — (Ph.D. thesis)