# Prove that the Möbius ladder and the toroidal ladder are non-isomorphic graphs.

I just gave this problem on my graph theory final, and I can't wait to see what innovative approaches my students come up with.

The two ladders are defined to be the only $3$-regular graphs that can be obtained by adding two new edges to the $2\times n$ grid, where $n\ge 3$. (The names suggest which ladder is which.)

So the problem is to prove that ${\mathcal T}_n$ (toroidal ladder) is not isomorphic to ${\mathcal M}_n$ (Möbius ladder) for each $n\ge 3$.

For even $n$ the toroidal ladder is bipartite, the Möbius ladder is not. For odd $n$ the Möbius ladder is bipartite, the toroidal ladder is not.