Math Problem Statement

Let G be a planar Eulerian graph. Consider some planar drawing of G. Show that there exists a closed Eulerian tour that never crosses itself in the considered drawing (it may touch itself at vertices but it never “crosses over to the other side”).

Solution

To show that there exists a closed Eulerian tour in a planar Eulerian graph GG that does not cross itself in a planar drawing, we can leverage several key properties of planar graphs and Eulerian circuits:

Step-by-Step Proof

  1. Planar and Eulerian Properties: Since GG is given as a planar Eulerian graph, it can be embedded in the plane without edge crossings (planarity), and each vertex in GG has an even degree (Eulerian property). By Euler's theorem, an Eulerian circuit (a closed tour visiting every edge exactly once) exists for GG because it is connected and all vertices have even degree.

  2. Face-Based Traversal: A planar graph can be drawn in such a way that every edge belongs to the boundary of exactly two faces (regions in the plane divided by the graph's edges). Since GG is Eulerian, every face in this planar embedding has an even number of edges around its boundary. This fact can be used to construct a non-crossing tour.

  3. Constructing the Non-Crossing Tour: We can construct a non-crossing Eulerian circuit by tracing the edges of the graph along the boundaries of faces in a continuous, cyclic manner. Begin at any vertex and traverse the boundary of the face that the initial edge belongs to, moving along the perimeter of this face until you return to the starting vertex.

  4. Ensuring Non-Crossing: Since each face boundary has an even number of edges, we can keep moving from one face to an adjacent face without having to cross any previously traversed edge. This continuous movement from face to face allows the traversal to touch previously visited vertices but does not require any edge crossing, thus ensuring that the path remains non-crossing within the plane.

  5. Closure of the Eulerian Circuit: The process will eventually bring you back to the starting point, completing a closed tour. Since every edge has been used exactly once, this path forms an Eulerian circuit that does not cross itself.

Conclusion

By carefully following the boundaries of adjacent faces, we achieve a closed, non-crossing Eulerian tour of GG. This method guarantees that the Eulerian circuit touches vertices as needed but avoids crossing any edge or itself in the planar embedding.

Would you like a detailed example or more information on any specific part of the proof?


Here are some additional questions to explore this concept further:

  1. How does the even degree of vertices in an Eulerian graph ensure the existence of a closed tour?
  2. Why is it essential that the graph is planar for constructing a non-crossing Eulerian tour?
  3. How might the proof change if the graph were non-planar but still Eulerian?
  4. What are some applications of non-crossing Eulerian tours in graph theory or network design?
  5. Can this approach be used to find non-crossing Eulerian tours in higher-dimensional embeddings?

Tip: In planar graph problems, consider focusing on face boundaries and edge adjacencies, as they often provide insights into non-crossing tours or paths.

Ask a new question for Free

By Image

Drop file here or Click Here to upload

Math Problem Analysis

Mathematical Concepts

Graph Theory
Planar Graphs
Eulerian Circuits
Graph Embedding

Formulas

-

Theorems

Euler's Theorem on Eulerian Circuits
Planarity in Graph Theory

Suitable Grade Level

Undergraduate level (Grades 11-12 and beyond)