Teljes gráf

A teljes gráf olyan egyszerű gráf, amelynek minden csúcsa össze van kötve minden más csúccsal. Az n csúcsú teljes gráfot $K_{n}$-nel jelöljük Kazimierz Kuratowski lengyel matematikus emlékére.

10 szög
K10 – a 10 csúcsú teljes gráf
Névadó	Kazimierz Kuratowski
Csúcsok száma	n
Élek száma	$\textstyle {\frac {n(n-1)}{2}}$
Sugár	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{különben}}\end{array}}\right.$
Átmérő	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{különben}}\end{array}}\right.$
Derékbőség	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{különben}}\end{array}}\right.$
Kromatikus szám	n
Élkromatikus szám	n, ha n páratlan n − 1, ha n páros
Automorfizmusok	n! (Sn)
Spektrum	$\left\{{\begin{array}{lll}\emptyset &n=0\\\{0^{1}\}&n=1\\\{(n-1)^{1},-1^{n-1}\}&{\text{különben}}\end{array}}\right.$
Egyéb	reguláris
Jelölés	Kn

Tulajdonságok

• $K_{n}$ reguláris, minden csúcsának fokszáma $n-1$.
• $K_{n}$ összesen ${\binom {n}{2}}={\frac {n(n-1)}{2}}$ élt tartalmaz.
• a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a $K_{5}$ gráffal topologikusan izomorf részgráfot.
• $K_{n}$ az (n+1)-szimplex éleit adja.

Az első nyolc teljes gráf az alábbi ábrán látható:

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

További információk

• Andrásfai Béla: Gráfelmélet, Polygon Kiadó, Szeged, 1997.
• MathWorld: Complete Graph