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 wierzchołkach oznacza się przez .
Własności grafów pełnych Pełny graf o wierzchołkach posiada (lub ) krawędzi ( boków i przekątnych wielokąta). Pełny graf stopnia jest grafem regularnym stopnia Wszystkie grafy pełne są swoimi klikami. Żaden z grafów pełnych stopnia co najmniej nie jest planarny (wynika z twierdzenia Kuratowskiego).
Przykłady Poniżej przedstawione zostały pełne grafy o liczbie wierzchołków od do
Historia Powstały co najmniej dwa wyjaśnienia symbolu niektóre źródła podają, że litera 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.
Zobacz też Relacja spójna
Przypisy
Linki zewnętrzne [dostęp 2025-10-12]. Complete graph , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-10-12].
P