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”).

To show that there exists a closed Eulerian tour in a planar Eulerian graph \( G \) 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 \( G \) is given as a planar Eulerian graph, it can be embedded in the plane without edge crossings (planarity), and each vertex in \( G \) has an even degree (Eulerian property). By Euler's theorem, an Eulerian circuit (a closed tour visiting every edge exactly once) exists for \( G \) 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 \( G \) 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 \( G \). 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.

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').

Explore how to prove the existence of a non-crossing closed Eulerian tour in a planar Eulerian graph. This solution leverages key properties of Eulerian circuits and graph planarity to show how to construct a tour that avoids edge crossings in a planar embedding. Ideal for advanced high school and undergraduate students studying graph theory.

Math Problem Statement

Solution

Ask a new question for Free

By Image

Math Problem Analysis

Mathematical Concepts

Formulas

Theorems

Suitable Grade Level

Related Recommendation