Walks, trails and paths
Imagine standing on a vertex. You may move along any edge to a neighbouring vertex, then along another edge, and so on. The route you trace is called a walk. It's just a list of vertices where each one is joined by an edge to the next.
Walks can wander. They can come back to places they've already been and reuse edges, like a dog on an afternoon stroll. Often we want routes that are more disciplined, so mathematicians use three words with increasingly strict rules:
| Name | Repeat a vertex? | Repeat an edge? | Everyday picture |
|---|---|---|---|
| Walk | Allowed | Allowed | A wander around town |
| Trail | Allowed | Not allowed | A tour that never walks the same street twice |
| Path | Not allowed | Not allowed | A direct trip that never passes the same spot twice |
Every path is a trail, and every trail is a walk, but not the other way round. The length of any of these is the number of edges it uses, counting repeats.
Here are all three on the same graph, plus a cycle, which we'll meet next. The numbers on the pink edges show the order in which they're used.
Swipe or scroll sideways to step through.
A walk
A → B → E → D → A → B → C. Six steps. It visits A and B twice and even uses the edge A–B twice (steps 1 and 5). Walks are allowed to do that.
A trail
D → E → B → C → E → F. No edge is used twice, but the vertex E is visited twice. That makes it a trail, not a path.
A path
A → D → E → F. No vertex is repeated (so no edge can be either). This is a path of length 3.
A cycle
B → C → F → E → B. It returns to its start and repeats nothing else: a cycle of length 4.
startvisitededges used
Definitions
A walk is a sequence of vertices v0, v1, …, vk in which each consecutive pair is joined by an edge. Its length is k, the number of steps.
A trail is a walk with no repeated edge. A path is a walk with no repeated vertex.
Example: why the difference matters
A delivery driver planning a route cares about paths, because passing the same junction twice wastes time. A street sweeper cares about trails: every street must be swept, and sweeping one twice is wasteful, but crossing the same junction several times is fine. A tourist strolling aimlessly is on a walk. Unit 6 is all about trails that use every edge exactly once.
Useful fact
If there's a walk from u to v, there's also a path from u to v. Whenever a walk revisits a vertex, cut out the loop between the two visits. Repeat until nothing repeats. In the walk above, A → B → E → D → A → B → C visits A twice; cutting out the loop leaves A → B → C, a path.
Try it. In the graph above, is C → E → D → A → B → E → F a walk, a trail or a path?
Show answer
Check the edges: C–E, E–D, D–A, A–B, B–E, E–F all exist, so it's a walk. No edge appears twice, so it's a trail. But E appears twice, so it's not a path.
Cycles
A cycle is a route that comes back to where it started without repeating anything else on the way: no vertex except the start (which is also the end), and no edge. A cycle needs at least 3 vertices in a simple graph. With only two, you'd have to go out and back along the same edge.
The cycle B → C → F → E → B in the last frame has length 4. The same cycle can be written starting anywhere or going the other way round, as C → F → E → B → C or B → E → F → C → B. These all count as one cycle.
- A graph with no cycles at all is called acyclic. Acyclic connected graphs are so important they get Unit 3 to themselves: they're called trees.
- The length of the shortest cycle in a graph is its girth. A graph containing a triangle has girth 3.
Example: cycles in real life
A bus route that returns to its depot is a cycle. In a company's payment records, a cycle like A pays B, B pays C and C pays A can be a warning sign that money is being passed around to look like real business. Auditors search for exactly these cycles.
Try it. Find a cycle of length 3 in the graph above, and a cycle of length 5.
Show answer
Length 3: C → E → F → C (edges C–E, E–F, F–C). Length 5: A → B → C → E → D → A (edges A–B, B–C, C–E, E–D, D–A). There are others too.
Connected graphs and components
A graph is connected if you can get from every vertex to every other vertex by following edges. If some pair of vertices has no path between them, the graph is disconnected, and it falls apart into separate pieces.
Definition
The connected components (or just components) of a graph are its maximal connected pieces. "Maximal" means you can't add any more vertices to a piece and keep it connected.
A useful way to think about components: say two vertices are "reachable from each other" if there's a path between them. Then the components are exactly the groups of mutually reachable vertices. A connected graph is one with exactly one component.
Example: islands
Take a country with many islands. Towns are vertices and roads are edges. Every island's road network is (usually) one component, and you can't drive from one island to another. Add a bridge between two islands and two components merge into one. If engineers want everyone to be able to drive everywhere, they need to keep adding bridges until there's a single component.
How few edges can a connected graph have?
Start with n separate vertices: that's n components. Every edge you add can merge at most two components into one, so it reduces the count by at most 1. To get down to a single component, you need at least n − 1 edges.
Try it. How many components does this graph have? What is the smallest number of edges you'd need to add to make it connected?
Show answer
4 components: {1, 2, 3}, {4}, {5, 6, 7} and {8, 9}. Each new edge can merge at most two components, so you need at least 3 edges, for example 3–4, 4–5 and 7–8.
Distance
In a connected graph, there may be many paths between two vertices. The distance between them, written d(u, v), is the length of the shortest one: the fewest edges you need to cross. If there's no path at all, we say the distance is infinite.
Why can't an edge skip a column? Suppose x is at distance 1 and joined by an edge to y. Then you can reach y in at most 2 steps: get to x, then cross. So y is at distance at most 2. In general, neighbours' distances differ by at most 1. This observation is the heart of the breadth-first search algorithm in Unit 4, which finds distances by building these columns one at a time.
Distance behaves the way you'd expect a distance to behave:
- d(u, u) = 0, and d(u, v) > 0 when u ≠ v.
- It's symmetric: d(u, v) = d(v, u).
- The triangle inequality: d(u, w) ≤ d(u, v) + d(v, w). Going via v can never beat the best direct route.
Example: "degrees of separation"
On a social network, your friends are at distance 1 from you, friends of friends at distance 2, and so on. The idea that any two people on Earth are linked by about six steps comes from a 1960s experiment by the psychologist Stanley Milgram. People were asked to pass a letter towards a stranger using only personal acquaintances, and the letters that arrived took about six steps on average. Studies of modern online networks have found typical distances that are even shorter.
Try it. Using the figure above, what is d(a, g)? And d(c, d)?
Show answer
d(a, g) = 3, for example a → b → e → g. d(c, d) = 3, for example c → S → a → d or c → e → f → d. There's no route of length 2: c's neighbours are S and e, and neither of them is joined to d.
Eccentricity, radius and diameter
Distances let us describe the overall "size" of a connected graph.
- The eccentricity of a vertex is its distance to the vertex furthest away from it. It says how far out the worst-case trip from that vertex goes.
- The diameter of the graph is the largest eccentricity: the longest distance between any two vertices.
- The radius is the smallest eccentricity. A vertex achieving it is a centre, the best place to put something that everyone needs to reach quickly.
Example: where to build the fire station
In the graph above, S has eccentricity 3 (it's 3 steps from f and g). Vertex b does better: it's 1 step from S, a and e, and 2 steps from c, d, f and g. So b has eccentricity 2. No vertex can do better than 2: to be within 1 step of everything, a vertex would need all 7 others as neighbours. So the radius is 2 and b is a centre. A fire station at b reaches every part of town within 2 steps.
The diameter is 3: for example, d(a, g) = 3, and no two vertices are further apart.
Try it. What are the diameter and radius of the cycle C6? Of the path P5 (5 vertices in a row)? Of the star with one centre and 5 leaves?
Show answer
- C6: every vertex is 3 steps from the vertex opposite it, so all eccentricities are 3. Diameter = radius = 3.
- P5: the end vertices are 4 apart, so the diameter is 4. The middle vertex reaches everything in 2 steps, so the radius is 2.
- Star: any two leaves are 2 apart, so the diameter is 2. The centre is 1 step from everything, so the radius is 1.
Bridges and cut vertices
Some edges and vertices hold a network together. Take them away and it falls apart.
Before
After removing C–D
Definitions
A bridge (or cut edge) is an edge whose removal increases the number of components.
A cut vertex (or articulation point) is a vertex whose removal, together with all its edges, increases the number of components.
There's a neat way to recognise bridges:
Theorem
An edge is a bridge exactly when it does not lie on any cycle.
Why? If an edge u–v lies on a cycle, then even without it you can still get from u to v the long way round the cycle, so nothing gets disconnected. If it lies on no cycle, then it's the only route between u and v; any other route would combine with the edge to make a cycle. In the figure, every edge except C–D sits on a triangle or a square. C–D sits on no cycle, so it's the bridge.
Example: single points of failure
Network engineers hunt for bridges and cut vertices because they are single points of failure. If an office's only internet cable is a bridge, one digger cutting it takes the whole office offline. If a hub airport is a cut vertex for some regional airports, closing it strands them. The fix is always the same: add another link so the weak spot sits on a cycle.
Try it.
- In the friendship graph from Unit 1 (Ana, Ben, Cara, Dev, Eli, Fay), which edge is a bridge? Which vertex is a cut vertex?
- In a path Pn, which edges are bridges? In a cycle Cn?
Show answers
- The bridge is Eli–Fay: it's Fay's only connection. Eli is a cut vertex: remove Eli and Fay is cut off. Every other edge lies on a cycle (Ana–Ben–Cara or Ben–Cara–Eli–Dev).
- In a path, every edge is a bridge: there are no cycles at all. In a cycle, no edge is a bridge: every edge lies on the cycle itself.
How robust is a network?
Having no bridges and no cut vertices is a good start, but we can measure robustness more precisely. The key idea is to count how many separate routes exist between two points.
A graph is called k-connected if it stays connected no matter which k − 1 vertices you remove. So "2-connected" means "connected with no cut vertex". The figure's graph is 2-connected.
Menger's theorem (1927), informally
The smallest number of vertices you must remove to separate X from Y equals the largest number of routes from X to Y that share no vertices except X and Y.
This is a "min = max" theorem: the smallest way to break something equals the largest number of independent ways it works. You'll see the same pattern again in Unit 7 (matching) and Unit 8 (network flow), where the max-flow min-cut theorem is a close relative of Menger's theorem.
Example: building a resilient network
Data centres and power grids are often built to be at least 2-connected, so that any single failure leaves everything reachable. Critical systems aim higher. A 3-connected network survives any two failures at once.
Connectivity with one-way edges
In a directed graph, being able to get from u to v doesn't mean you can get back. Think of a city with one-way streets: you might be able to drive from the station to the hotel but not straight back.
- A directed graph is strongly connected if you can get from every vertex to every other vertex following the arrows.
- It's weakly connected if it would be connected after ignoring the directions (treating every arrow as a two-way street).
- Its strongly connected components are the maximal groups in which everyone can reach everyone, respecting directions.
The graph in the figure is weakly connected but not strongly connected. A, B, C form one strongly connected component (go round the cycle) and D, E form another.
Example: planning one-way streets
A town council wants to make every street one-way to reduce congestion, while still letting everyone drive from anywhere to anywhere. When is this possible? A beautiful theorem by Herbert Robbins (1939) gives the answer: exactly when the street network is connected and has no bridges. A bridge would have to point one way, cutting off the return trip. If every street lies on a cycle, you can orient the streets so the result is strongly connected.
Try it. In the figure, can you reach A from E? Add a single arrow to make the whole graph strongly connected.
Show answer
No: from E you can only go to D, and from D only back to E. Adding any arrow from the pink group back to the teal group fixes it. For example, add E → A: now A → B → C → D → E → A is a cycle through all five vertices, so everyone can reach everyone.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. A walk has length 7 and repeats a vertex. Explain why there must be a shorter path between the same two endpoints.
Show answer
If a vertex x appears twice, the part of the walk between its two visits is a loop that returns to x. Cutting it out leaves a walk between the same endpoints with at least one fewer step. Keep cutting until no vertex repeats; what's left is a path of length less than 7.
2. A graph has 10 vertices and 3 components. What is the smallest number of edges it could have?
Show answer
A component with k vertices needs at least k − 1 edges. Adding over the 3 components gives at least 10 − 3 = 7 edges.
3. True or false: if every vertex of a graph has degree at least 1, the graph is connected.
Show answer
False. Two separate edges (four vertices, each of degree 1) form a graph with no isolated vertices but two components.
4. What is the diameter of the complete graph K10? Of the complete bipartite graph K3,4?
Show answer
K10: every pair is adjacent, so the diameter is 1. K3,4: vertices on opposite sides are adjacent (distance 1), and two vertices on the same side share a neighbour on the other side (distance 2). So the diameter is 2.
5. Can a vertex of degree 1 ever be a cut vertex? Can an edge touching a vertex of degree 1 fail to be a bridge?
Show answer
A degree-1 vertex is never a cut vertex: removing it leaves the rest of its component connected, because no path between two other vertices passes through a leaf. The edge touching it is always a bridge (as long as the other end exists): removing it isolates the leaf.
6. A town's street map has exactly one bridge. Can the council make every street one-way and still let everyone reach everywhere?
Show answer
No. By Robbins' theorem, it needs a connected network with no bridges. Whichever way the bridge points, people on the far side can never get back across. The council must either keep that street two-way or build another link so the bridge lies on a cycle.
Summary and glossary
- A walk follows edges freely; a trail never reuses an edge; a path never revisits a vertex. If there's a walk between two vertices, there's a path.
- A cycle returns to its start without repeating anything else. Graphs without cycles are acyclic.
- A graph splits into connected components. A connected graph on n vertices needs at least n − 1 edges.
- Distance is the length of a shortest path. Eccentricity, radius and diameter summarise how spread out a graph is.
- Bridges and cut vertices are single points of failure. An edge is a bridge exactly when it lies on no cycle.
- In directed graphs, strong connectivity means every vertex can reach every other following the arrows.
- Walk
- A sequence of vertices, each joined to the next by an edge.
- Trail
- A walk that never repeats an edge.
- Path
- A walk that never repeats a vertex.
- Cycle
- A closed route with at least 3 vertices that repeats nothing but its start.
- Connected
- Every vertex can reach every other.
- Component
- A maximal connected piece of a graph.
- Distance
- The length of a shortest path between two vertices.
- Eccentricity
- A vertex's distance to the vertex furthest from it.
- Diameter
- The largest distance between any two vertices.
- Radius
- The smallest eccentricity; achieved at a centre.
- Bridge
- An edge whose removal disconnects part of the graph.
- Cut vertex
- A vertex whose removal disconnects part of the graph.
- Strongly connected
- In a directed graph, every vertex can reach every other along the arrows.