5
$\begingroup$

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$.

$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Exactly. This is the simplest and most direct solution (also the solution I came up with). Nicely done. $\endgroup$
    – Doc
    Dec 15, 2013 at 15:24
  • $\begingroup$ Thanks. It is a nice problem, not too hard to solve, but not immediately obvious either. Please report elegant solutions by your students (if they are different). $\endgroup$
    – Leen Droogendijk
    Dec 15, 2013 at 15:55
  • $\begingroup$ Also, one is planar and the other is not. $\endgroup$
    – hbm
    Dec 16, 2013 at 3:26
  • $\begingroup$ @hbm Absolutely, and this was the most common response I received among students who got at least partial credit. Few were actually able to prove this however. Many just stated it. $\endgroup$
    – Doc
    Dec 19, 2013 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.