Demuestra que la escalera de Möbius y la escalera toroidal son grafos no isomorfos.

Question

Acabo de poner este problema en mi examen final de teoría de grafos, y estoy deseando ver qué enfoques innovadores se les ocurren a mis alumnos.

Las dos escaleras están definidas para ser las únicas $3$ -regulares que se pueden obtener añadiendo dos nuevas aristas a la $2\times n$ de la red, donde $n\ge 3$ . (Los nombres sugieren qué escalera es cada una).

Así que el problema es demostrar que ${\mathcal T}_n$ (escalera toroidal) no es isomorfa a ${\mathcal M}_n$ (escalera de Möbius) para cada $n\ge 3$ .

Answer 1

Incluso para $n$ la escalera toroidal es bipartita, la escalera de Möbius no. Para impar $n$ la escalera de Möbius es bipartita, la escalera toroidal no lo es.