Eulerian graphs

Understanding Eulerian Graphs

• An Eulerian graph is a specific type of graph in which it is possible to traverse every edge exactly once without lifting the pen off the paper. This path is called an Eulerian circuit or Eulerian cycle.
• A semi-Eulerian graph allows a path (an Eulerian path) that traverses every edge exactly once but unlike an Eulerian cycle, it does not start and end at the same vertex.
• These types of graphs are named after the Swiss mathematician Leonhard Euler who developed graph theory while solving the Konigsberg Bridge Problem in the 18th century.

Properties of Eulerian Graphs

• An Eulerian graph must be connected, where there’s a path between each pair of vertices, and every one of its vertices has an even degree (the number of edges incident to the vertex).
• For a graph to have an Eulerian path (be semi-Eulerian), it must be connected and have either zero or exactly two vertices of odd degree. The Eulerian path would then start and end on the vertices of odd degree (if there are any).
• These conditions guarantee that you can move into a vertex via one edge and exit from it via another edge, enabling the traversal of every edge exactly once.

Euler’s Theorems for Eulerian Graphs

• Euler’s Theorem for Eulerian cycles specifies that a graph has an Eulerian cycle if and only if the graph is connected and each vertex has even degree.
• Euler’s Theorem for Eulerian paths states that a graph has an Eulerian path but not an Eulerian cycle if and only if it has exactly two vertices of odd degree.

Constructing Eulerian Circuits and Paths

• Constructing an Eulerian circuit or path involves starting at a suitable vertex, moving along edges, and erasing them as you go.
• For a graph with an Eulerian cycle, it doesn’t matter where you start; for a semi-Eulerian graph, you need to start at one of the vertices with an odd degree.
• If you get stuck during this process and still have edges left, it means the graph was not Eulerian or semi-Eulerian. If you complete the graph and end up at your starting point with an Eulerian cycle or at the other odd degree vertex with an Eulerian path, the graph was indeed Eulerian or semi-Eulerian.