Graf pełny

Graf pełny – graf prosty, nieskierowany, w którym dla każdej pary węzłów istnieje krawędź je łącząca.

Graf pełny o $n$ wierzchołkach oznacza się przez $K_n$. Niektóre źródła podają, że litera $K$ pochodzi od niemieckiego słowa komplett, lecz niemiecki termin vollständiger Graph, oznaczający graf pełny, nie zawiera nawet tej litery. Inne źródła stwierdzają, że tę notację przyjęto w uznaniu zasług Kazimierza Kuratowskiego dla teorii grafów.

Własności grafów pełnych

• Pełny graf o $n$ wierzchołkach posiada $\frac{n(n-1)}{2}$ (lub $(\genfrac{}{}{0ex}{}{n}{2})$) krawędzi ($n$ boków i $\frac{n(n-3)}{2}$ przekątnych wielokąta).
• Pełny graf stopnia $n$ jest grafem regularnym stopnia $n-1.$
• Wszystkie grafy pełne są swoimi klikami.
• Żaden z grafów pełnych stopnia co najmniej $5$ nie jest planarny (wynika z twierdzenia Kuratowskiego).

Przykłady

Poniżej przedstawione zostały pełne grafy o liczbie wierzchołków od $1$ do $8:$

• 
  $K_1$
• 
  $K_2$
• 
  $K_3$
• 
  $K_4$
• 
  $K_5$
• 
  $K_6$
• 
  $K_7$
• 
  $K_8$