Повний граф

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

Властивості

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

Нижче подані зображення повних графів з кількістю вершин від 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}$

Див. також

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