Teljes páros gráf

A teljes páros gráf olyan páros gráf, ahol mindkét partíció minden csúcsára fennáll, hogy össze van kötve a másik partíció minden csúcsával.

Definíció

Teljes páros gráfnak nevezünk valamely $G:=(V_{1}+V_{2},E)$ páros gráfot, ha bármely $v_{1}\in V_{1}$ és $v_{2}\in V_{2}$ csúcspárra létezik $\{v_{1},v_{2}\}\in E$ él.

$K_{m,n}$ szimbólummal jelöljük azt a páros teljes gráfot, ahol $\left|V_{1}\right|=m$ és $\left|V_{2}\right|=n$. A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.

Példák

• 
  K_1,3
• 
  K_2,3
• 
  K_3,3

Tulajdonságok

• a $K_{m,n}$ gráf $m+n$ csúcsot és $m\cdot n$ élet tartalmaz
• a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a $K_{3,3}$ gráffal topológikusan izomorf részgráfot.
• a $K_{m,n}$ gráf összefüggő

Lásd még

• Páros gráf
• Teljes gráf