Úplný graf

V teorii grafů se termínem úplný graf označuje takový neorientovaný graf, v němž jsou každé dva vrcholy spojené hranou. Označuje se $K_n$, kde n je počet jeho vrcholů

Definice

Graf G = (V, E) je úplný, pokud $|E| = {\left | V\right |\choose 2}$. Z toho plyne, že úplný graf o n vrcholech má právě $\frac{n(n - 1)}{2}$ hran.

Vlastnosti

• je to regulární graf stupně n - 1
• je to maximálně souvislý graf, protože jediný vrcholový řez, který z něj učiní nesouvislý graf, je celá množina vrcholů
• žádný rovinný graf nemůže obsahovat úplný graf o více než 4 vrcholech (tedy $K_5$ a vyšší)

Příklady

Úplné grafy na 1 až 8 vrcholech:

• 

  K₁

• 

  K₂

• 

  K₃

• 

  K₄

• 

  K₅

• 

  K₆

• 

  K₇

• 

  K₈