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

        100px 100px 100px 100px        120px 120px 120px 120px

 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 

Kategória:Teória grafov