Introduction to Graph Theory - Part 4

In the previous parts, we learned how to describe graphs mathematically and explored several important graph classes. Now it's time to actually move through a graph. How do we get from one vertex to another? What does it mean for a graph to be "connected"? And how does all of this relate to Euler's bridge problem from Part 1? Let's find out.

Walks

Imagine you're exploring a city by walking along its streets. You start at some intersection, walk to the next one, then the next, and so on. You might even pass through the same intersection more than once — that's perfectly fine. In graph theory, this kind of journey is called a walk.

Definition 13. A walk in a graph $G = (V, E)$ is a sequence of vertices $v_0, v_1, \ldots, v_k$ such that $(v_i, v_{i+1}) \in E$ for all $0 \leq i < k$. The number $k$ is called the length of the walk.

Notice that a walk places no restrictions on repetition — you are free to visit the same vertex or cross the same edge as many times as you like. The walk $1, 2, 3, 2, 1$ is perfectly valid in a graph that contains the edges $(1,2)$ and $(2,3)$.

But sometimes, we want to be more disciplined about our journey. This leads us to two more restrictive notions.

Trails and Paths

What if we want to avoid crossing the same street twice, but we don't mind passing through the same intersection again? This gives us a trail.

Definition 14. A trail in a graph $G$ is a walk in which no edge is repeated.

And if we want to be even more strict — never visiting the same intersection twice — we get a path.

Definition 15. A path in a graph $G$ is a walk in which no vertex is repeated¹.

Since no vertex is repeated in a path, no edge can be repeated either. Therefore, every path is also a trail, and every trail is also a walk. But the reverse is not true: the walk $1, 2, 3, 2$ is a trail (no edge is repeated) but not a path (vertex $2$ appears twice).

We can also talk about closed versions of these concepts. A walk (or trail, or path) is called closed if the first and last vertex are the same — in other words, you end up where you started. A closed trail has a special name that will become important shortly: it is called a circuit. And a closed path — where the only repeated vertex is the start/end — is called a cycle².

The Handshaking Lemma

Before we talk about connectivity, let's prove a beautiful result that connects degrees and edges. We already hinted at this in Part 3 when counting the edges of a complete graph: each edge contributes exactly $2$ to the total degree sum, because it has two endpoints. This gives us the Handshaking Lemma.

Lemma 1 (Handshaking Lemma). For any graph $G = (V, E)$, we have $\sum_{v \in V} d(v) = 2|E|$.

Proof. Every edge $e = (u, w) \in E$ contributes exactly $1$ to the degree of $u$ and exactly $1$ to the degree of $w$. Therefore, each edge contributes exactly $2$ to the total sum of degrees. Since there are $|E|$ edges, the total sum of degrees is $2|E|$.

The name comes from a fun real-world interpretation: if a group of people shake hands, and we count the total number of handshakes each person participated in, the result is always even — because every handshake involves two people.

This simple lemma has a surprisingly useful consequence.

Corollary 1. In any graph, the number of vertices with odd degree is even.

Proof. The sum $\sum_{v \in V} d(v) = 2|E|$ is always even. If there were an odd number of vertices with odd degree, the sum could not be even — a contradiction.

Connected Graphs

So far, we've talked about moving through a graph, but we haven't addressed a fundamental question: can we always get from one vertex to another? In some graphs, the answer is yes — but in others, the graph might "fall apart" into separate pieces.

Definition 16. A graph $G$ is connected if for every pair of vertices $u, v \in V$, there exists a path from $u$ to $v$.

All the complete graphs $K_n$ are connected — you can go from any vertex to any other in a single step. Every tree is connected by definition. But consider the graph $G = (\{1,2,3,4\}, \{(1,2), (3,4)\})$: there is no path from vertex $1$ to vertex $3$, so this graph is not connected.

When a graph is not connected, it naturally splits into separate "islands" that have no edges between them. These are called connected components.

Definition 17. A connected component of a graph $G$ is a maximal connected subgraph of $G$. In other words, it is a connected subgraph that is not contained in any larger connected subgraph.

The graph $G = (\{1,2,3,4\}, \{(1,2), (3,4)\})$ from above has two connected components: one containing vertices $\{1, 2\}$ and one containing vertices $\{3, 4\}$. A connected graph has exactly one connected component — the entire graph itself.

Observation 4. Every vertex of a graph belongs to exactly one connected component.

This might seem obvious, but it's worth stating: the connected components partition the vertex set of the graph into disjoint groups. No vertex is left out, and no vertex belongs to two different components.

Euler Paths and Circuits

Now we can finally revisit the Königsberg Bridge Problem from Part 1 with our formal toolkit. Euler asked: can we cross every bridge exactly once? In our language, this means finding a trail that uses every edge. Such a trail has a special name.

Definition 18. An Euler trail (or Euler path) is a trail that visits every edge of the graph exactly once.

Definition 19. An Euler circuit is a closed Euler trail — an Euler trail that starts and ends at the same vertex.

A graph that has an Euler circuit is called Eulerian. A graph that has an Euler trail (but not necessarily an Euler circuit) is called semi-Eulerian.

Euler's great insight, which we described informally in Part 1, can now be stated as a precise theorem. And interestingly, the Handshaking Lemma's corollary plays a key role.

Theorem 1 (Euler, 1736). A connected graph $G$ has an Euler circuit if and only if every vertex has even degree. It has an Euler trail (but no Euler circuit) if and only if it has exactly two vertices of odd degree.

Let's verify this with Königsberg. The four landmasses had degrees $3, 3, 3$, and $5$ — all odd. Since there are four vertices of odd degree (not zero, not two), Euler's theorem tells us there is neither an Euler circuit nor an Euler trail. The walk is impossible, just as Euler concluded almost three centuries ago.

The "if" direction of this theorem — showing that an Euler circuit exists when all degrees are even — can be proved constructively by building the circuit step by step. We will discuss this algorithm in a later part.

Hamiltonian Paths and Cycles

Euler trails visit every edge exactly once. But what if we want to visit every vertex exactly once instead? This seemingly small change leads to a fundamentally different kind of problem.

Definition 20. A Hamiltonian path is a path that visits every vertex of the graph exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once.

The name honors Sir William Rowan Hamilton, who in 1857 posed the challenge of finding such a cycle on the edges of a dodecahedron. At first glance, Hamiltonian and Eulerian problems look similar, but they behave very differently.

For Euler trails, we have a clean characterization: just check the degrees. For Hamiltonian paths, no such simple criterion exists. Determining whether a graph has a Hamiltonian path is one of the most famous hard problems in computer science — it is NP-complete, meaning that no efficient algorithm is known³.

To see the contrast, consider the complete graph $K_5$: it has both an Euler circuit (every vertex has degree $4$, which is even) and a Hamiltonian cycle (just visit the vertices in order $1, 2, 3, 4, 5$ and return to $1$). But the Petersen graph, which we met in Part 3, has no Hamiltonian cycle despite being $3$-regular — a fact that is surprisingly hard to prove.

Looking Ahead

We now have a solid understanding of how to move through graphs and what it means for a graph to be connected. In the next part, we will take a closer look at trees — the connected graphs without cycles that we briefly introduced in Part 3. Trees have many beautiful properties and equivalent characterizations, and they play a central role in both theory and applications.