Ú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ť .

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

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

Vlastnosti 
Počet hrán úplného grafu  je .
Každý úplný graf je silno regulárny graf.
Chromatické číslo úplného grafu  je .
 Úplný graf  je -regulárny.
 Úplný graf  má  automorfizmov.
 Úplný graf  má práve  rôznych kostier (tzv. Cayleyho vzorec).

Iné projekty 

Teória grafov