7.1 Eulerian circuits and trails

Eulerian circuits and trails are fascinating graph structures that traverse every edge exactly once. They're named after Leonhard Euler, who solved the famous Seven Bridges of Königsberg problem in 1736, laying the foundation for graph theory.

To have an Eulerian circuit, all vertices must have even degree and the graph must be connected. For an Eulerian trail, exactly two vertices need odd degree. Algorithms like Hierholzer's and Fleury's help construct these paths efficiently.

Eulerian Circuits and Trails

Definition of Eulerian circuits and trails

• Eulerian trail traverses every edge exactly once allowing repeated vertices starts and ends at different vertices (Seven Bridges of Königsberg)
• Eulerian circuit forms closed path visiting every edge once starts and ends at same vertex (Tour of a museum)
• Concept named after Leonhard Euler originated from Königsberg bridge problem in 1736 laid foundation for graph theory

Conditions for Eulerian paths

• Eulerian circuit requires all vertices have even degree and graph is connected excluding isolated vertices (Complete graph $K_4$)
• Eulerian trail needs exactly two vertices with odd degree others even and graph connected excluding isolated vertices (Path graph $P_4$)
• Degree of vertex counts number of edges incident to it determines Eulerian properties
• Connected graph ensures path exists between any two vertices crucial for Eulerian paths

Identification of Eulerian graphs

• Check Eulerian circuit:
  1. Verify graph connectivity
  2. Count degree of each vertex
  3. Ensure all vertices have even degree
• Determine Eulerian trail:
  1. Verify graph connectivity
  2. Count degree of each vertex
  3. Confirm exactly two vertices have odd degree
• Empty graph considered to have Eulerian circuit while single vertex graph has trivial Eulerian circuit

Construction of Eulerian circuits

• Hierholzer's algorithm builds Eulerian circuit:
  1. Start at any vertex
  2. Follow unused edges until returning to start
  3. Repeat for vertices with unused edges
  4. Combine circuits
• Fleury's algorithm constructs Eulerian path:
  1. Start at odd degree vertex for trail
  2. Choose edges that maintain connectivity
  3. Remove used edges progressively
• Eulerian trail construction starts at odd degree vertex applies chosen algorithm ends at other odd degree vertex
• Consider time complexity and efficiency when handling large graphs ($O(E)$ for Hierholzer, $O(E^2)$ for Fleury)