Euler and Hamilton Paths

Euler Paths and Circuits

Definition

An Euler circuit in a graph $G$ is a simple circuit containing every edge of $G$. An Euler path is a simple path containing every edge of $G$.

Undirected Graphs

Condition for Euler Circuit

A connected graph has an Euler circuit if and only if every vertex has even degree.

Intuitive Explantion

Imagine you're walking around a graph and using each edge exactly once. If you enter a vertex on one edge, you must also leave it on another edge at some point. To guarantee you can always leave a vertex, it needs to have an even number of "in-out" edges. If you can travel through all edges, you also must end up at your starting vertex, thus the need for every vertex having even degree in the case of Euler circuits.

Condition for Euler Path

A connected graph has an Euler path if and only if every vertex has an even degree (in which case it is also an Euler circuit) or exactly two vertices have an odd degree.

Intuitive Explantion

With an Euler path, you start at one vertex and end at a different one. These start and end vertices are the only exceptions. The start vertex needs one "out" edge more than "in" edges. The end vertex will have one more "in" edge than "out" edge. Therefore, these two vertices must have an odd degree. All the other vertices, which can be entered and exited, must have an even degree.

Directed Graphs

Condition for Euler Circuit

A strongly connected directed graph (where there is a direct path between every pair of vertices) has an Euler circuit if and only if the in-degree equals the out-degree for every vertex.

Condition for Euler Path

 A weakly connected directed graph (where we ignore the edge directions and treat it as having paths between all vertices) has an Euler path if and only if only one of the following two cases is met:

• The in-degree equals the out-degree for every vertex, which means it also has an Euler circuit.
• There is exactly one vertex with out-degree = in-degree + 1 (start vertex) and exactly one vertex with in-degree = out-degree + 1 (end vertex), and the in-degree equals the out-degree for every other vertex.

Hamilton Paths and Circuits

Definition

A simple path in a graph $G$ that passes through every vertex exactly once is called a Hamilton path, and a simple circuit in a graph $G$ that passes through every vertex exactly once is called a Hamilton circuit.

Necessary (But Not Sufficient) Conditions

Connectivity

A Hamiltonian path or circuit requires the graph to be connected. If the graph is in disconnected, every vertex cannot be visited from a single starting point.

Minimal Degree

• Hamiltonian Circuit: In general, the minimum degree of a vertex should be at least 2. In a Hamiltonian circuit, vertex must be connected to at least two other vertices (so you can get in and out of it).
• Hamiltonian Path: The minimum degree of vertex should be 1 because start and end vertices, in a Hamiltonian path, will typically have degree value at least of 1.

Sufficient (But Not Necessary) Conditions

1. Dirac's Theorem: If a graph has $n$ vertices (where $n\ge 3$), and the degree of every vertex is at least $n/2$, then the graph has a Hamiltonian circuit.
2. Ore's Theorem: If a graph has $n$ vertices (where $n\ge 3$), and for every pair of non-adjacent vertices $u$ and $v$, the sum of their degrees is greater than or equal to $n$, then the graph has a Hamiltonian circuit.
3. Special Cases: Every complete graph with $3$ or more vertices always has a Hamiltonian circuit. To find it, you just need to visiting all vertices in a linear form, and then return to the first vertex. For example, in $K_4$, a Hamiltonian circuit could be ($1-2-3-4-1$).