Úplný (kompletní) graf je graf, ve kterém každá dvojice vrcholů je sousední. Kompletní graf s n vrcholy označujeme Kn.