Ú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ť ${\displaystyle K_{n}\ }$.

Grafy ${\displaystyle K_{1}\ }$ až ${\displaystyle 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.

${\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}$

Vlastnosti

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

Iné projekty

• Commons ponúka multimediálne súbory na tému Úplný graf

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.