Möbius ladder
In graph theory, the Möbius ladder , for even numbers , is formed from an -cycle by adding edges (called "rungs") connecting opposite pairs of vertices in the cycle. It is a cubic circulant graph, so-named because (with the exception of (the utility graph ), has exactly four-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by . Properties. For every even , the Möbius ladder is a nonplanar apex graph, meaning that it cannot be drawn without crossings in the plane but removing one vertex allows the  remaining graph to be drawn without crossings. These graphs have crossing number one, and can be embedded without crossings on a torus or projective plane. Thus, they are examples of toroidal graphs. explores embeddings of these graphs onto higher genus surfaces. Möbius ladders are vertex-transitive – they have symmetries taking any vertex to any other vertex – but (with the exceptions of and ) they are not edge-transitive. The edges from the cycle from which the ladder is formed can be distinguished from the rungs of the ladder, because each cycle edge belongs to a single 4-cycle, while each rung  belongs to two such cycles. Therefore, there is no symmetry taking a cycle edge to a rung edge or vice versa. When "n" ≡ 2 (mod 4), "M" is bipartite. When "n" ≡ 0 (mod 4), it is not bipartite. The endpoints of each rung are an even distance apart in the initial cycle, so adding each rung creates an odd cycle. In this case, because the graph is 3-regular but not bipartite, by Brooks' theorem it has chromatic number 3. show that the Möbius ladders are uniquely determined by their Tutte polynomials. The Möbius ladder "M" has 392  spanning trees; it and "M" have the most spanning trees among all cubic graphs with the same number of vertices. However, the 10-vertex cubic graph with the most spanning trees is the Petersen graph, which is not a Möbius ladder. The Tutte polynomials of the Möbius ladders may be computed by a simple recurrence relation. Graph minors. Möbius ladders play an important role in the theory of graph minors. The earliest result of this type is a theorem of that graphs with no "K" minor can be formed by using clique-sum operations to combine planar graphs and the  Möbius ladder "M"; for this reason "M" is called the Wagner graph. Chemistry and physics. first synthesized molecular structures in the form of a Möbius ladder, and since then this structure has been of interest in chemistry and chemical stereography, especially in view of the ladder-like form of DNA molecules. With this application in mind, studies the mathematical symmetries of embeddings of Möbius ladders in R. In particular, as she shows, every three-dimensional embedding of a Möbius ladder with an odd number of rungs is topologically chiral: it cannot be converted into its mirror image by a  continuous deformation of space without passing one edge through another. On the other hand, Möbius ladders with an even number of rungs all do have embeddings into R that can be deformed into their mirror images. Möbius ladders have also been used as the shape of a superconducting ring in experiments to study the effects of conductor topology on electron interactions. Combinatorial optimization. Möbius ladders have also been used in computer science, as part of integer programming approaches to problems of set packing and linear ordering. Certain configurations within these problems can be used to define facets of the polytope  describing a linear programming relaxation of the problem; these facets are called Möbius ladder constraints.