Úplný graf

Úplný graf alebo kompletný graf je graf, v ktorom je každý vrchol grafu spojený s každým iným vrcholom grafu. Úplný graf s n vrcholmi sa zvykne označovať $K_n$.

Grafy $K_1$ až $K_4$ sú rovinné grafy. Ostatné úplné grafy nie sú rovinné.

Úplné grafy pre 1 až 8 vrcholov, číslo za dvojbodkou je počet hrán.

$K_1:0$	$K_2:1$	$K_3:3$	$K_4:6$
$K_5:10$	$K_6:15$	$K_7:21$	$K_8:28$

Vlastnosti

• Počet hrán úplného grafu $K_n$ je $n(n-1)/2$.
• Každý úplný graf je silno regulárny graf.
• Chromatické číslo úplného grafu $K_n$ je $n$.
• Úplný graf $K_n$ je $(n-1)$-regulárny.
• Úplný graf $K_n$ má $n!$ automorfizmov.
• Úplný graf $K_n$ má práve $n^{n-2}$ rôznych kostier (tzv. Cayleyho vzorec).