Ú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