Graphs and Networks: Eulerian graphs

Graphs and Networks: Eulerian graphs

Eulerian Graphs

Basic Characteristics

  • An Eulerian graph is a graph where each vertex has an even degree. This means every vertex has an even number of edges connected to it.
  • A graph is considered Eulerian if it contains an Eulerian circuit. That is a closed path that covers every edge once and only once.

Eulerian Path and Eulerian Circuit

  • An Eulerian path, unlike an Eulerian circuit, does not need to finish at the same node where it started. However, it still must pass through every edge exactly once.
  • For a graph to contain an Eulerian path, exactly two vertices must have odd degrees. These vertices are the start and end points of the Eulerian path.
  • If all vertices have even degree, the graph contains an Eulerian circuit.

Constructing Eulerian Circuits and Paths

  • A practical method to construct an Eulerian path or circuit is Fleury’s Algorithm. This algorithm requires erasing edges from the graph one by one in a specific manner until the Eulerian path or circuit is formed.
  • Hierholzer’s Algorithm is another efficient method to find the Eulerian circuit in a connected graph. It involves creating cycles and linking them together.

Fundamental Theorem of Eulerian Graphs

  • The Fundamental Theorem of Eulerian Graphs states two key characteristics of Eulerian graphs:
    1. If all vertices in a connected graph have even degree, the graph is Eulerian - it contains an Eulerian circuit.
    2. If only two vertices in a connected graph have odd degrees and the rest have even degrees, the graph contains an Eulerian path.

Applications

  • Eulerian paths and circuits have several real-world applications, such as designing efficient routes for garbage collection, postal delivery, and plowing. This stems from the principle of covering every path with the least repetition.
  • Eulerian graphs also find uses in data structure and algorithm design, such as bridging routes in a computer network or circuit design in electronics.

Properties

  • The study of Eulerian graphs leads to the development of several graph theories and concepts, including the concept of graph cycle, graph’s degree sequence, bridge, and edge connectivity.
  • An Eulerian trail or walk is a trail in a finite graph that uses every edge exactly once. Unlike an Eulerian path or circuit, an Eulerian trail can start and end on different vertices.
  • A graph that has an Eulerian trail but not an Eulerian circuit is called a semi-Eulerian graph.
  • Every Eulerian graph is connected, but not every connected graph is Eulerian.