Polni graf
Iz Wikipedije, proste enciklopedije
Pólni gráf (redko tudi popólni gráf) je v teoriji grafov graf, v katerem vsaka povezava povezuje par njegovih točk (vozlišč), oziroma kjer so vse točke povezane vsaka z vsako. Poln graf na n točkah se označuje s Kn. Število povezav je enako:
.
Polni graf je regularen stopnje n-1. Vsi polni grafi so maksimalno povezani, saj je točkovni prerez grafa, s katerim grafi postanejo nepovezani, kar celotna množica njegovih točk. Ravninski graf ne more vsebovati subdivizije K5 (ali polnega dvodelnega grafa K3,3) kot podgrafa (izrek Kuratowskega). K4 je torej največji polni graf, ki je še ravninski.
Polne grafe običajno rišemo v obliki pravilnega mnogokotnika. Polni grafi na n točkah pri n med 1 in 8 so prikazani spodaj:

