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$.

Példák

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

Tulajdonságok

Síkbarajzolható gráf nem tartalmazhat a $K_{3,3}$ gráffal topológikusan izomorf részgráfot.

Lásd még

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