Connectivity, Euler and Hamilton paths

This week’s question is usually in two parts: “Does this graph have an Euler circuit / Euler path?” and “Does it have a Hamilton circuit?”. The Euler part is entirely degree counting; the Hamilton part is trial and error plus a few theorems. A definition question on connectivity and a short shortest-path (Dijkstra) question may also come. It is not on the midterm, it is a final exam topic.

Golden rules:

1. Euler = edges, Hamilton = vertices. Mixing them up is the most expensive mistake.
2. In a connected graph, an Euler circuit exists $\iff$ every degree is even. An Euler path (without a circuit) exists $\iff$ exactly two vertices have odd degree.
3. For Hamilton there is no general “if and only if” criterion. To say one exists, write the circuit or use Dirac/Ore; to say none exists, show an obstacle.
4. A question on the number of paths $\Rightarrow$ a power of the adjacency matrix.

Paths and circuits

In Rosen’s language (the terms of this course):

Intuition: vertices are stations on the field, edges are running lines. A training course is a path; if you return to the station you started from, it is a circuit.

Counting paths with matrices

If $A$ is the adjacency matrix, the number of paths of length $r$ from $v_i$ to $v_j$ is $(A^r)_{ij}$. Why: $(A^2)_{ij} = \sum_k a_{ik}a_{kj}$, that is, the number of intermediate vertices $k$ with an edge from $i$ to $k$ and from $k$ to $j$.

For the 4-vertex graph in the questions:

$A^2 = \begin{bmatrix} 2&1&2&1\\ 1&3&1&2\\ 2&1&2&1\\ 1&2&1&3 \end{bmatrix}$

The diagonal gives the degrees: a path of length 2 that leaves $v_i$ and comes back = going along an edge and returning.

Connectivity

An undirected graph is connected if there is a path between every two vertices. A graph that is not connected splits into components: maximal connected subgraphs. An isolated vertex is a component by itself.

A cut vertex: a vertex whose deletion (together with its edges) increases the number of components. A bridge (cut edge): an edge whose deletion increases the number of components.

TIP · the bridge test. If an edge is on a cycle, it cannot be a bridge, because the rest of the cycle still connects its two ends. First mark the cycles, then check the remaining edges.

Measures:

• Vertex connectivity $\kappa(G)$: the minimum number of vertices that must be deleted to disconnect the graph (or reduce it to a single vertex).
• Edge connectivity $\lambda(G)$: the minimum number of edges that must be deleted to disconnect it.
• Always $\kappa(G) \le \lambda(G) \le \min_v \deg(v)$.

Examples: $\kappa(K_n) = \lambda(K_n) = n-1$; $\kappa(K_{m,n}) = \min(m,n)$; if there is a bridge then $\lambda = 1$, if there is a cut vertex then $\kappa = 1$.

In directed graphs: if for every $a, b$ there are directed paths both $a\to b$ and $b\to a$, the graph is strongly connected; if it becomes connected when you ignore directions, it is weakly connected.

Euler circuits and paths

An Euler circuit: a simple circuit that uses every edge exactly once. An Euler path: a simple path that uses every edge exactly once.

The story: the 7 bridges of Königsberg. 4 land masses (vertices), 7 bridges (edges), degrees $5, 3, 3, 3$. Euler showed that there is no tour crossing each bridge once.

Theorem. In a connected multigraph with at least two vertices:

• An Euler circuit exists $\iff$ every vertex has even degree.
• An Euler path exists but no circuit $\iff$ exactly two vertices have odd degree. The path starts and ends at these two vertices.

Intuition: every time the tour passes through a vertex, it enters along one edge and leaves along another: it adds 2 to the degree. So every vertex other than the start and end must have even degree.

A fully written proof (necessary condition)

Claim. If a connected multigraph $G$ has an Euler circuit, then every vertex of $G$ has even degree.

Proof. Let the Euler circuit start and end at $a$, and follow it. The first edge contributes 1 to $\deg(a)$. Each time the circuit passes through a vertex $v$ (including returns to $a$ before the end), it enters $v$ along one edge and leaves along another, contributing 2 to $\deg(v)$. The last edge enters $a$ and contributes 1 more to $\deg(a)$. Since the circuit uses every edge exactly once, these contributions count every edge end exactly once. Hence $\deg(a) = 1 + 2t + 1$ for some integer $t \ge 0$, which is even, and every other vertex has degree equal to a sum of 2’s, which is even. $\blacksquare$

In plain words: follow the circuit, each “pass-through” adds 2 to a vertex; the starting vertex gets 1 + 1 from the first and last edges. The reverse direction (if every degree is even there is a circuit) is a constructive proof: build a circuit, find new circuits from the remaining edges and splice them in (Hierholzer). On the final, usually the necessary condition or only the application of the theorem is asked.

Application example. The “butterfly” graph: $ab, bc, ca, cd, de, ec$ (two triangles with the common vertex $c$).

degrees: a 2, b 2, c 4, d 2, e 2   -> all even, connected
Euler circuit: a, b, c, d, e, c, a
Hamilton circuit? c is a cut vertex (deleting it separates {a,b} and {d,e})
  -> you would have to pass through c twice -> NO Hamilton circuit

The same graph is perfect for Euler and impossible for Hamilton. The best example showing that the two concepts are independent.

Hamilton paths and circuits

A Hamilton path: a simple path that passes through every vertex exactly once. A Hamilton circuit: a circuit that returns to its starting vertex and passes through every other vertex exactly once.

Unlike Euler, there is no known simple “if and only if” condition for a Hamilton circuit (the problem is NP-complete). You have two kinds of tools.

Showing one exists (sufficient conditions):

These conditions are sufficient but not necessary: in $C_{10}$ the degrees are 2 and the conditions fail, but $C_{10}$ itself is a Hamilton circuit.

Showing none exists (obstacles):

1. If there is a vertex of degree 1, there is no Hamilton circuit (entering and leaving that vertex needs 2 edges).
2. Both edges of a vertex of degree 2 are forced in the circuit. If three forced edges meet at one vertex, or they close a small incomplete circuit, that is a contradiction.
3. If there is a cut vertex, there is no Hamilton circuit.
4. In a bipartite graph whose sides are not the same size, there is no Hamilton circuit.

Special graphs: $K_n$ ($n\ge 3$) always has a Hamilton circuit, and the number of different circuits is $\frac{(n-1)!}{2}$. $Q_n$ ($n \ge 2$) has a Hamilton circuit: a Gray code (consecutive codes differ in one bit) is exactly a Hamilton circuit in $Q_n$.

PITFALL · Using the Euler condition for Hamilton. “All degrees are even, so there is a Hamilton circuit” is wrong. In the butterfly graph all degrees are even but there is no Hamilton circuit. Conversely, in $K_4$ the degrees are 3 (odd) but there is a Hamilton circuit.

Shortest path: Dijkstra (briefly)

The length of a shortest path between two vertices in a weighted graph. Dijkstra’s algorithm (when there are no negative weights):

1. Give the start the label 0 and the others $\infty$.
2. Among the vertices not yet finalized, choose the one with the smallest label and finalize it.
3. Update the labels of its neighbors: $L(v) = \min\big(L(v),\ L(u) + w(u,v)\big)$.
4. Repeat until the target is finalized.

For the graph in the question, the order of finalizing:

a:0  ->  c:2  ->  b:3  ->  d:8  ->  e:10  ->  z:13
path (trace back): z <- e <- d <- b <- c <- a   length 13

Note: the first label of $b$ is 4 (edge $ab$), but 3 via $c$. A vertex’s label can drop before it is finalized; once finalized it does not change. The complexity is $O(n^2)$.

Common mistakes