Homeomorfisme de grafos

En Teoria de grafos, es diu que dos grafos $G_1$ i $G_2$ són homeomorfos si abdós poden obtindre's a partir d'un mateix grafo per una successió de subdivisions elementals d'arestes. Sol notar-se per $G_1{\cong }_H{G}_2$.

Este concepte, de naturalea combinatòria, està relacionat en el concepte topològic d'homeomorfisme: qualsevol grafo pot representar-se com un espai topològic en que cada vèrtiç queda representat per un punt distint i cada aresta per un arc homeomorfo en l'interval [0,1]. Dos grafos són homeomorfos en el sentit de la teoria de grafos si i solament si ho són com a espais topològics.

Eixemple

Tots els grafos cicle de n vèrtiços són homeomorfos entre sí. Per eixemple, si es fa una subdivisió elemental d'algun vèrtiç de $C_4$ s'obté un $C_5$. Finalment, si al $C_5$ se li aplica novament una subdivisió elemental es conseguix el $C_6$. Com a tant $C_5$ i $C_6$ es varen obtindre de $C_4$ es diu que $C_5$ és homeomorfo a $C_6$ i es nota $C_5{\cong }_H{C}_6$

• 
  $C_4$
• 
  $C_5$
• 
  $C_6$