Unit 2: Walks, Paths, Circuits, Eulerian Graphs & Hamiltonian Cycles

1. Hierarchy of Graph Traversals

Traversals across vertices and edges are characterized by the restrictions imposed on repeated vertices and repeated edges:

Definition 2.1 (Walk): A walk $W$ of length $k$ from vertex $u$ to vertex $v$ (a $u$-$v$ walk) in a graph $G$ is an alternating sequence of vertices and edges:

such that $v_0 = u$, $v_k = v$, and each edge $e_i$ has endpoints $v_{i-1}$ and $v_i$. In simple graphs, edges are uniquely determined by endpoints, so a walk is denoted simply by the vertex sequence $(v_0, v_1, \dots, v_k)$.

• Closed Walk: A walk where $v_0 = v_k$ (starts and terminates at the identical vertex).
• Open Walk: A walk where $v_0 \ne v_k$.

Definition 2.2 (Trail and Circuit):

1. A trail is a walk in which no edge is repeated (all $e_i$ are distinct). Vertices may be repeated.
2. A circuit is a closed trail ($v_0 = v_k$ with no repeated edges).

Definition 2.3 (Path and Cycle):

1. A path (or simple path) is an open walk in which no vertex is repeated (and consequently no edge is repeated).
2. A cycle (or simple circuit) is a closed walk $(v_0, v_1, \dots, v_k = v_0)$ of length $k \ge 3$ in which all intermediate vertices $v_0, v_1, \dots, v_{k-1}$ are distinct.

| Traversal Type | Repeated Vertices? | Repeated Edges? | Open / Closed | | :--- | :--- | :--- | :--- | | Walk | Allowed | Allowed | Either | | Trail | Allowed | Forbidden | Open | | Circuit | Allowed | Forbidden | Closed | | Path | Forbidden | Forbidden | Open | | Cycle | Ends Only ($v_0 = v_k$) | Forbidden | Closed ($k \ge 3$) |

2. The Walk-Path Reduction Lemma

Lemma 2.1 (Every Walk Contains a Path): If a graph $G$ contains a walk of length $k$ connecting vertex $u$ to vertex $v$, then $G$ contains a simple path connecting $u$ to $v$ of length at most $k$.

Complete Proof (by Well-Ordering Principle):

Let $S$ be the set of lengths of all $u$-$v$ walks in $G$. By hypothesis, $k \in S$, so $S \subseteq \mathbb{Z}_{\ge 0}$ is non-empty. By the Well-Ordering Principle of non-negative integers, $S$ contains a minimum element; call it $m \le k$. Let $P = (u = v_0, v_1, \dots, v_m = v)$ be a $u$-$v$ walk of minimum length $m$. We claim that $P$ is a simple path (i.e., all vertices are distinct). Suppose for contradiction that $P$ repeats a vertex: $v_i = v_j$ for some $0 \le i < j \le m$. Then we can excise the sub-walk between $v_i$ and $v_j$, yielding:

Notice that $P'$ is a valid $u$-$v$ walk in $G$. The length of $P'$ is $m - (j - i) < m$. This directly contradicts the minimality of $m$! Therefore, $P$ cannot contain any repeated vertices. Hence $P$ is a simple path of length $m \le k$. $\blacksquare$

1. Connectedness in Undirected Graphs

Definition 2.4 (Connected Graph): Two vertices $u, v \in V(G)$ are said to be connected if there exists a $u$-$v$ path in $G$. A graph $G$ is called a connected graph if every pair of distinct vertices in $G$ is connected. Otherwise, $G$ is called disconnected.

2. The Connected Component Equivalence Relation

Theorem 2.1 (Connectivity as an Equivalence Relation): Define a binary relation $\sim$ on the vertex set $V(G)$ by:

(with $u \sim u$ trivially via a path of length 0). Then $\sim$ is an equivalence relation on $V(G)$.

Complete Proof:

1. Reflexivity: For any $u \in V$, the trivial single-vertex path $(u)$ shows $u \sim u$.

2. Symmetry: Suppose $u \sim v$. Then there exists a path $P = (u = v_0, v_1, \dots, v_k = v)$.

Reversing the sequence gives $P^{-1} = (v = v_k, v_{k-1}, \dots, v_0 = u)$, which is a valid $v$-$u$ path. Thus $v \sim u$.

3. Transitivity: Suppose $u \sim v$ and $v \sim w$.

Then there exists a $u$-$v$ walk and a $v$-$w$ walk. Concatenating these two walks yields a $u$-$w$ walk. By Lemma 2.1, this walk contains a simple $u$-$w$ path. Thus $u \sim w$. Therefore, $\sim$ is an equivalence relation. $\blacksquare$

Definition 2.5 (Connected Components): The equivalence classes of $V(G) / \sim$ induce maximal connected subgraphs called the connected components of $G$. The number of connected components of $G$ is denoted by $\omega(G)$ or $k(G)$. A graph $G$ is connected if and only if $\omega(G) = 1$.

1. Eulerian Circuits and Trails

Named after Leonhard Euler's seminal 1736 paper resolving the Königsberg bridges problem:

Definition 2.6 (Eulerian Circuit and Trail):

1. An Eulerian trail (or Euler path) in a graph $G$ is a trail that traverses every edge of $G$ exactly once.
2. An Eulerian circuit (or Euler tour) is a closed trail that visits every edge of $G$ exactly once.
3. A graph $G$ is called Eulerian if it contains an Eulerian circuit.
4. A graph $G$ is called semi-Eulerian if it contains an open Eulerian trail (but no Eulerian circuit).

2. Euler's Characterization Theorem

Theorem 2.2 (Euler's Theorem for Eulerian Graphs): Let $G$ be a connected graph (or a graph whose non-trivial components contain all edges).

1. $G$ is Eulerian if and only if every vertex of $G$ has even degree:

1. $G$ contains an open Eulerian trail if and only if it has exactly two vertices of odd degree. In this case, the trail must originate at one odd-degree vertex and terminate at the other.

Complete Formal Proof of Part 1:

• $(\implies)$ Necessity:

Suppose $G$ has an Eulerian circuit $C$. Let $v \in V(G)$. Every time the circuit enters vertex $v$ via some edge, it must depart from $v$ via a distinct, previously unused edge. Since $C$ traverses every edge of $G$ exactly once, the edges incident with $v$ are partitioned into pairs (one entry edge, one exit edge). If $v$ is the starting and ending vertex of $C$, the initial departure and final entry also form a pair. Therefore, the number of incident edges $\deg(v)$ is twice the number of times $C$ visits $v$:

Hence $\deg(v)$ is even for every vertex.

• $(\impliedby)$ Sufficiency (by induction on $|E|$):

Assume every vertex in the connected graph $G$ has even degree, and $|E| \ge 1$.

• Step 1 (Existence of a Cycle):

Since $G$ is connected and has at least one edge, and no vertex has degree 0 or 1 (all degrees are even and $\ge 2$), by Theorem 1.3, $G$ must contain at least one simple cycle $C_1$.

• Step 2 (Decomposition):

Remove all edges of $C_1$ from $G$, forming the subgraph $G' = G - E(C_1)$. In $C_1$, each vertex has degree 2 (or 0). Thus, for every $v \in V(G')$:

Every vertex in $G'$ still has even degree!

• Step 3 (Inductive Splicing):

By induction hypothesis, each connected component of $G'$ has an Eulerian circuit. Since $G$ was connected, each component of $G'$ shares at least one vertex with the cycle $C_1$. We traverse $C_1$, and whenever we encounter a vertex belonging to a component of $G'$, we detour and traverse that component's Eulerian circuit before resuming $C_1$. The combined traversal visits every edge of $G$ exactly once and returns to the origin. Thus $G$ contains an Eulerian circuit. $\blacksquare$

3. Fleury's Algorithm for Constructing an Euler Circuit

Definition 2.7 (Bridge): A bridge (or cut-edge) in a connected graph is an edge whose deletion increases the number of connected components: $\omega(G - e) > \omega(G)$.

Fleury's Algorithm:

1. Start at any vertex $v_0$ (if $G$ has two odd vertices, start at one of them).
2. At current vertex $v_i$, choose an incident edge $e = \{v_i, v_{i+1}\}$ according to the Golden Rule:

Never cross a bridge unless there is no alternative edge available.

1. Traverse edge $e$, erase $e$ from $G$, and remove any isolated vertices produced.
2. Set $v_i \leftarrow v_{i+1}$ and repeat until all edges have been traversed.

1. The Instant Insanity Puzzle Formulation

The puzzle consists of four cubes, each having its six faces colored with four distinct colors: Red (R), Green (G), Blue (B), and White (W). The objective is to stack the four cubes in a vertical $1 \times 1 \times 4$ tower such that all four colors appear on each of the four sides of the tower (Front, Back, Left, Right).

A brute-force search over all orientations requires testing:

Using graph theory, the solution can be derived analytically in minutes!

2. Graph-Theoretic Modeling

Construct a multigraph $G$ where:

• The vertices are the four colors: $V = \{R, G, B, W\}$.
• For each cube $i \in \{1, 2, 3, 4\}$, draw three edges labeled $i$ connecting the colors of opposite pairs of faces:
• Edge 1: (Top, Bottom) colors of cube $i$.
• Edge 2: (Front, Back) colors of cube $i$.
• Edge 3: (Left, Right) colors of cube $i$.

The composite multigraph $G$ has $4$ vertices and $4 \times 3 = 12$ edges (3 edges for each label $1, 2, 3, 4$).

3. The Decomposition Theorem for Instant Insanity

Theorem 2.3 (Solution Criterion): A solution to the Instant Insanity puzzle exists if and only if the graph $G$ contains two edge-disjoint subgraphs $H_1$ (Front-Back) and $H_2$ (Left-Right) such that:

1. Both $H_1$ and $H_2$ are 2-regular graphs (spanning all 4 color vertices, where every vertex has degree 2).
2. Both $H_1$ and $H_2$ contain exactly one edge with each label $1, 2, 3, 4$.
3. $E(H_1) \cap E(H_2) = \emptyset$ (no shared edges).

Why this yields the solution:

• Since each $H_k$ is 2-regular on 4 vertices, it decomposes into either a 4-cycle $C_4$ or two 2-cycles $2 C_2$.
• Orienting the cycles in $H_1$ specifies which face is Front and which is Back for each cube.
• Because every vertex has in-degree 1 and out-degree 1 in the oriented 2-regular subgraph, each color appears exactly once in the Front column and once in the Back column!
• Similarly, $H_2$ independently determines Left and Right faces with all four colors present.

1. Hamiltonian Paths and Cycles

In stark contrast to Eulerian paths (which visit every edge), Hamiltonian paths visit every vertex:

Definition 2.8 (Hamiltonian Path and Cycle):

1. A Hamiltonian path in a graph $G$ is a simple path that visits every vertex of $G$ exactly once.
2. A Hamiltonian cycle in $G$ is a simple cycle that visits every vertex of $G$ exactly once and returns to the starting vertex.
3. A graph $G$ is called Hamiltonian if it contains a Hamiltonian cycle.

While determining whether a graph is Eulerian is solvable in linear time $\mathcal{O}(|V| + |E|)$ via degree parity, determining whether a graph is Hamiltonian is famously NP-complete.

2. Ore's Theorem and Dirac's Theorem

Although no simple necessary and sufficient condition exists, powerful degree conditions guarantee Hamiltonicity:

Theorem 2.4 (Ore's Theorem, 1960): Let $G$ be a simple graph with $n \ge 3$ vertices. If for every pair of distinct non-adjacent vertices $u, v \in V(G)$:

then $G$ is Hamiltonian.

Corollary 2.1 (Dirac's Theorem, 1952): Let $G$ be a simple graph with $n \ge 3$ vertices. If the minimum degree satisfies:

then $G$ is Hamiltonian.

Proof of Dirac's Theorem from Ore's Theorem:

If $\delta(G) \ge n/2$, then for any two non-adjacent vertices $u, v$:

Ore's condition holds immediately, so $G$ is Hamiltonian. $\blacksquare$

3. The Bondy-Chvátal Closure Theorem

Definition 2.9 (Graph Closure): The closure of a graph $G$ of order $n$, denoted $[G]$ or $\text{cl}(G)$, is obtained by repeatedly connecting pairs of non-adjacent vertices $u, v$ satisfying $\deg(u) + \deg(v) \ge n$, until no such pairs remain.

Theorem 2.5 (Bondy-Chvátal Theorem, 1976): A graph $G$ is Hamiltonian if and only if its closure $\text{cl}(G)$ is Hamiltonian. In particular, if $\text{cl}(G) = K_n$ (the complete graph), then $G$ is Hamiltonian.

4. The Traveling Salesperson Problem (TSP)

Definition 2.10 (Traveling Salesperson Problem): Given a complete weighted graph $K_n$ with non-negative edge costs $c(u, v) \ge 0$, find a Hamiltonian cycle that minimizes the total traversal cost:

• Metric TSP: Edge weights satisfy the Triangle Inequality: $c(u, w) \le c(u, v) + c(v, w)$.
• Christofides-Serdyukov Algorithm: Provides a polynomial-time 1.5-approximation ratio for Metric TSP using Minimum Spanning Trees and minimum-weight perfect matchings on odd-degree vertices.