Teljes gráf

Sablon:Gráf infobox 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.

Tulajdonságok

• $K_n$ reguláris, minden csúcsának fokszáma $n-1$.
• $K_n$ összesen $(\genfrac{}{}{0ex}{}{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