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 ${\displaystyle n}$ wierzchołkach oznacza się przez ${\displaystyle K_{n}}$^[1].

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

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

• 
  ${\displaystyle K_{1}}$
• 
  ${\displaystyle K_{2}}$
• 
  ${\displaystyle K_{3}}$
• 
  ${\displaystyle K_{4}}$
• 
  ${\displaystyle K_{5}}$
• 
  ${\displaystyle K_{6}}$
• 
  ${\displaystyle K_{7}}$
• 
  ${\displaystyle K_{8}}$

Powstały co najmniej dwa wyjaśnienia symbolu ${\displaystyle K_{n}:}$

• niektóre źródła podają, że litera ${\displaystyle K}$ pochodzi od niemieckiego słowa komplett^[2], 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^[3].

• Relacja spójna

• Eric W.E.W. Weisstein Eric W.E.W., Complete Graph, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2025-10-12].
• Complete graph (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-12].