# 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.