Teljes gráf

10 szög
K10 – a 10 csúcsú teljes gráf
Névadó	Kazimierz Kuratowski
Csúcsok száma	n
Élek száma	${\displaystyle \textstyle {\frac {n(n-1)}{2}}}$
Sugár	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{különben}}\end{array}}\right.}$
Átmérő	${\displaystyle \left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{különben}}\end{array}}\right.}$
Derékbőség	${\displaystyle \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	${\displaystyle \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

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 ${\displaystyle K_{n}}$-nel jelöljük Kazimierz Kuratowski lengyel matematikus emlékére.

Tulajdonságok

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

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

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

További információk

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