Homeomorfismo de grafos

En Teoría de grafos, se dice que dos grafos ${\displaystyle G_{1}}$ y ${\displaystyle 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 ${\displaystyle 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.

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 ${\displaystyle C_{4}}$ se obtiene un ${\displaystyle C_{5}}$. Finalmente, si al ${\displaystyle C_{5}}$ se le aplica nuevamente una subdivisión elemental se logra el ${\displaystyle C_{6}}$. Como tanto ${\displaystyle C_{5}}$ y ${\displaystyle C_{6}}$ se obtuvieron de ${\displaystyle C_{4}}$ se dice que ${\displaystyle C_{5}}$ es homeomorfo a ${\displaystyle C_{6}}$ y se nota ${\displaystyle C_{5}\cong _{H}C_{6}}$

• 
  ${\displaystyle C_{4}}$
• 
  ${\displaystyle C_{5}}$
• 
  ${\displaystyle C_{6}}$