Escalera de Möbius

Para cada n > 4 par, la escalera de Möbius Mn es un grafo de ápice no plano, lo que significa que no se puede dibujar sin cruces en el plano, pero al eliminar un vértice se puede dibujar el grafo restante sin cruces.

Las escaleras de Möbius son vértices-transitivas (tienen simetrías que llevan cualquier vértice a cualquier otro vértice), pero (con las excepciones de M4 y M6) no son isotoxales.

Los puntos finales de cada peldaño están separados por una distancia uniforme en el ciclo inicial, por lo que agregar cada peldaño crea un ciclo impar.

En este caso, debido a que el grafo es 3-regular pero no bipartito, por el teorema de Brooks se puede afirmar que posee coloración 3.De Mier y Noy (2004) demostró que las escaleras de Möbius están determinadas únicamente por sus polinomios de Tutte.

Ciertas configuraciones dentro de estos problemas se pueden usar para definir facetas del politopo que describen una relajación en la programación lineal del problema; estas facetas se denominan restricciones de escalera de Möbius.