Is there an easy way to tell if a graph can be embedded on a Möbius strip (with no edges crossing)?
A specific version of this: if a simple graph with an odd number of vertices has all vertices of degree 4, can it be embedded on a Möbius strip?
Answer summary:
- There are 103 forbidden subgraphs for the Möbius strip that are explicitly known and drawn on page 212ff of Dan Archdeacon's thesis.
- There are 35 forbidden minors for the Möbius strip, they are explicitly known, and even better there are only 6 cubic forbidden minors, each with an intuitive explanation.
I have not yet answered the second question, but Jim Belk's excellent explanation has given me good ideas.