Halin’s Theorem for the Mobius Strip

Abstract

Halin’s Theorem characterizes those locally finite infinite graphs that embed in the plane without accumulation points by giving a set of six topologically-excluded subgraphs. We prove the analogous theorem for graphs that embed in an open Möbius strip without accumulation points. There are \(153\) such obstructions under the ray ordering defined herein. There are \(350\) obstructions under the minor ordering. There are \(1225\) obstructions under the topological ordering. The relationship between these graphs and the obstructions to embedding in the projective plane is similar to the relationship between Halin’s graphs and \(\{K_5, K_{3,3}\}.^1\)