Paths and Circuits

Definitions

Walk

A sequence of vertices where consecutive vertices are adjacent. $v_0, e_1, v_1, e_2, v_2, \ldots, e_k, v_k$

Length: number of edges

Trail

A walk with no repeated edges.

Path

A walk with no repeated vertices (and thus no repeated edges).

Circuit (Closed Walk)

A walk that starts and ends at the same vertex.

Cycle

A circuit with no repeated vertices except start/end.

Connectivity

Distance

$d(u, v)$ = length of shortest path between $u$ and $v$ (or $\infty$ if no path exists).

Diameter

Maximum distance between any two vertices: $\text{diam}(G) = \max_{u,v \in V} d(u,v)$

Eccentricity

For vertex $v$: $e(v) = \max_{u \in V} d(v, u)$

Radius

$\text{rad}(G) = \min_{v \in V} e(v)$

Center

Vertices with eccentricity equal to radius.

Euler Paths and Circuits

Euler Path

A trail that visits every edge exactly once.

Euler Circuit

An Euler path that starts and ends at the same vertex.

Existence Conditions

Undirected Graph:

Type	Condition
Euler circuit	Connected + all vertices have even degree
Euler path (not circuit)	Connected + exactly 2 vertices have odd degree

Directed Graph:

Type	Condition
Euler circuit	Strongly connected + $d^+(v) = d^-(v)$ for all $v$
Euler path	Weakly connected + one vertex has $d^+ = d^- + 1$, one has $d^- = d^+ + 1$, all others have $d^+ = d^-$

Fleury's Algorithm (Finding Euler Path/Circuit)

1. Start at appropriate vertex
2. Walk edges, removing them as you go
3. Only cross a bridge if no other option

Hierholzer's Algorithm (More Efficient)

1. Start at any vertex, follow edges until returning to start
2. If unvisited edges remain from vertices in current path:
   • Start new cycle from such a vertex
   • Splice into main path
3. Repeat until all edges visited

Time complexity: $O(|E|)$

Hamiltonian Paths and Circuits

Hamiltonian Path

A path that visits every vertex exactly once.

Hamiltonian Circuit (Cycle)

A Hamiltonian path that starts and ends at the same vertex.

No Simple Conditions!

Unlike Euler paths/circuits, there's no simple criterion.

Sufficient Conditions

Ore's Theorem: If $G$ has $n \geq 3$ vertices and for every pair of non-adjacent vertices $u, v$: $d(u) + d(v) \geq n$ then $G$ has a Hamiltonian circuit.

Dirac's Theorem: If $G$ has $n \geq 3$ vertices and every vertex has: $d(v) \geq \frac{n}{2}$ then $G$ has a Hamiltonian circuit.

Necessary Conditions

If $G$ has a Hamiltonian circuit:

• $G$ is connected
• Every vertex has degree $\geq 2$
• Removing any vertex leaves a connected graph

Complexity

Finding Hamiltonian paths/circuits is NP-complete.

Comparison: Euler vs. Hamilton

Property	Euler	Hamilton
Visits	Every edge once	Every vertex once
Easy to check?	Yes (degree conditions)	No (NP-complete)
Named after	Leonhard Euler (1736)	William Hamilton (1859)

The Seven Bridges of Königsberg

Classic problem solved by Euler (1736):

• City with 2 islands
• 7 bridges connecting landmasses
• Can you walk crossing each bridge exactly once?

Answer: No. The graph has 4 vertices, all with odd degree. Euler path requires 0 or 2 odd-degree vertices.

This problem initiated graph theory.

Applications

Euler Paths/Circuits

• Snow plow routing (cover all streets)
• DNA sequencing (de Bruijn graphs)
• Drawing figures without lifting pen

Hamiltonian Paths/Circuits

• Traveling Salesman Problem
• Circuit board design
• Scheduling problems

Traveling Salesman Problem (TSP)

Given a weighted complete graph, find the minimum-weight Hamiltonian circuit.

Complexity

• NP-hard
• No known polynomial algorithm

Approximations

• Nearest neighbor heuristic
• 2-opt improvement
• Christofides algorithm (3/2 approximation for metric TSP)