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 ${\tfrac {n(n-1)}{2}}$ (lub ${\tbinom {n}{2}}$) krawędzi ($n$ boków i ${\tfrac {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}$