Homeomorfismo de grafos

Plantilla:Distinguir En Teoría de grafos, se dice que dos grafos $G_1$ y $G_2$ son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas. Suele notarse por $G_1{\cong }_H{G}_2$.

Este concepto, de naturaleza combinatoria, está relacionado con el concepto topológico de homeomorfismo: cualquier grafo puede representarse como un espacio topológico en que cada vértice queda representado por un punto distinto y cada arista por un arco homeomorfo con el intervalo [0,1]. Dos grafos son homeomorfos en el sentido de la teoría de grafos si y solo si lo son como espacios topológicos.

Ejemplo

Todos los grafos ciclo de n vértices son homeomorfos entre sí. Por ejemplo, si se hace una subdivisión elemental de algún vértice de $C_4$ se obtiene un $C_5$. Finalmente, si al $C_5$ se le aplica nuevamente una subdivisión elemental se logra el $C_6$. Como tanto $C_5$ y $C_6$ se obtuvieron de $C_4$ se dice que $C_5$ es homeomorfo a $C_6$ y se nota $C_5{\cong }_H{C}_6$

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