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.

Algorithm for Finding an Euler Circuit

This algorithm is based on the idea of building up an Euler circuit by repeatedly splicing cycles together. It works under the assumption that the graph is connected and every vertex has an even degree. The method can be summarized as follows:

1. Initialization:
   • Choose an arbitrary vertex as the "start vertex".
2. Cycle Finding and Marking:
   • Find a cycle starting and ending at the "start vertex" by traversing unmarked edges.
   • Mark all edges in this cycle. This cycle is now our “current circuit.”
3. Iteration/Splicing:
   • Check for Unmarked Edges: Search the current circuit vertices for a vertex that has unmarked edges incident to it. If no such vertex is found, stop and the current circuit is a full Euler circuit.
   • Find Another Cycle: If such a vertex is found, find a random cycle that starts and ends at this vertex using only unmarked edges.
   • Splicing: "Splice" the newly found cycle into the current circuit to create a new, larger current circuit. The new circuit also begins and ends at the original start vertex.
   • Repeat step 3, by returning to Check for Unmarked Edges, using the new current circuit.
4. Termination:
   • The algorithm terminates when there are no vertices in the current circuit with unmarked edges incident to them.

See here

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$).