Question

(i) Let \(G\) be a non-planar graph that can be drawn without crossings on a Möbius strip. Prove that, with the usual notation, \(n-m+f=1\). (ii) Show how \(K_{5}\) and \(K_{3,3}\) can be drawn without crossings on the surface of a Möbius strip.

Short answer

For any graph \(G\) which can be drawn without crossings on a Möbius strip, the relation \(n-m+f=1\) holds. This is derived by subtly altering Euler's formula for planar graphs. The graphs \(K_5\) and \(K_{3,3}\) can both be drawn on a Möbius strip without any crossings, proving that they can actually be considered 'non-planar'.

Step-by-step solution

Proving the formula

Consider a planar graph transformation into a Möbius strip by connecting two edges into a single edge, effectively removing a face. It's easy to see that one less edge \(e\) and one less face \(f\) leads to the equation \(n-(m-1)+(f-1) = n-m+f = 2-1=1\), which is the equation we wanted to prove.

Drawing \(K_5\)

In order to draw the graph \(K_5\) on a Möbius strip, start by drawing a pentagon for the five vertices on one side of the strip. Then draw a diagonal line within the pentagon to every other vertex without crossings. When the need arises to connect a vertex with another that would ordinarily require crossing, instead draw an edge around the Möbius strip back to the original vertex.

Drawing \(K_{3,3}\)

Start by drawing three vertices on one edge of the Möbius strip and the other three on the other edge. Draw straight lines to connect every vertex from one edge to each vertex on the other edge. Use two edges on the surface and the fourth one around, whenever crossing would occur.

Key concepts

Non-Planar Graphs

Graphs are often classified as planar or non-planar based on whether they can be drawn on a plane without edges crossing. Non-planar graphs, like the complete graph \(K_5\) or the complete bipartite graph \(K_{3,3}\), cannot be drawn in such a manner without some of their edges intersecting. This characteristic is essential in graph theory to understand constraints on graph visualization in two-dimensional spaces.

When dealing with non-planar graphs, the equation \(n - m + f = 1\) or \(n - m + f = 2\) often arises in relation to surfaces like the Möbius strip, where \(n\) is the number of vertices, \(m\) is the number of edges, and \(f\) is the number of faces. This helps to understand their properties and limitations when drawn on different surfaces.

Möbius Strip

The Möbius strip is a fascinating surface in topology with the unique property of having only one side and one boundary. Visualizing a graph on a Möbius strip is different than on a plane because of its one-sided nature.

This surface allows certain non-planar graphs, such as \(K_5\) and \(K_{3,3}\), to be embedded without crossings, which would be impossible on a regular plane.

For those familiar with graph theory, the Möbius strip challenges traditional notions, offering a playground where seemingly impossible embeddings are realized.

Graph Embedding

Graph embedding is the process of illustrating a graph in a given space, such as a plane or a Möbius strip, in such a way that no edges intersect, except possibly at their endpoints. This task becomes interesting when working with complex graphs and surfaces that offer more creative solutions like the Möbius strip.

Techniques to embed graphs often involve strategic placements of vertices and intelligent use of the surface properties. These solutions invite unique problem-solving approaches to discover embeddings once thought impossible, enabling exploration of graph theory's spatial characteristics.

Complete Graph K5

A complete graph \(K_5\) has five vertices, with each vertex connected to every other vertex. This results in a dense graph structure with ten edges.

In regular planar drawing, \(K_5\) cannot be represented without edges crossing; however, when considered on a Möbius strip, it's possible to achieve a crossing-free embedding by using the strip's unique property of having one continuous surface.

By manipulating the Möbius strip's surface, one can effectively use more space and routes for connecting vertices, making \(K_5\) an intriguing study of non-planar graph embedding.

Complete Bipartite Graph K3,3

The complete bipartite graph \(K_{3,3}\) consists of two sets of three vertices. Every vertex in each set connects to all vertices in the other set, creating a total of nine edges. This graph is extensive in fields like computer science and network modeling due to its unique connections.

Like \(K_5\), the \(K_{3,3}\) graph cannot be drawn without crossings in a standard plane. However, on a Möbius strip, utilizing its peculiar surface allows for a neat crossing-free layout.

The Möbius strip's capacity to encompass differently-connected vertices into a singular line results in a seamless illustration of \(K_{3,3}\), revealing the graph's elegance when freed from conventional plane constraints.