1
Walk, path and cycle differ by repetition
A walk may repeat anything; a path repeats no vertex; a cycle is a path that returns to its start.
Lesson · Graphs and Trees · Structure
Paths and Connectivity
Reachability partitions the vertices into components. Cut vertices and bridges are the single points of failure, and the number of edges needed for connectivity is exactly n − 1.
walk any sequence of edges; may repeat
path a walk with no repeated VERTEX
cycle a closed path of length ≥ 3
connected: every pair joined by a path
The vocabulary, precisely
Core ideas
What this lesson establishes
The three words are used loosely in conversation and precisely here, and several theorems depend on the distinction.
2
Reachability is an equivalence relation
Reflexive, symmetric and transitive, so by “Equivalence Relations and Partitions” in Sets, Relations, and Functions it partitions the vertices — and the blocks are the components.
3
Connectivity needs at least n − 1 edges
Each edge can reduce the component count by at most one, and you start with n components.
The material
Connectivity
The vocabulary, components as classes, and the two kinds of weak point.
Definition · Walk, path, cycle
A walk is a sequence of vertices with consecutive ones adjacent. A path is a walk with no repeated vertex. A cycle is a walk of length at least 3 that starts and ends at the same vertex and repeats no other. A graph with no cycle is acyclic.
Theorem · Walks contain paths
If there is a walk from u to v, there is a path from u to v.
Take a shortest walk from u to v. If it repeated a vertex w, the section between the two visits to w could be deleted, giving a shorter walk — contradicting minimality. So it repeats no vertex and is a path.
□
This small theorem is used constantly: it means questions about reachability may be answered with walks, which are easier to build, and the answer transfers to paths.
Definition · Connected, components
A graph is connected if every pair of vertices is joined by a path. A component is a maximal connected subgraph.
Theorem · Components partition the vertices
"Is joined by a path to" is an equivalence relation on V, and its classes are exactly the components.
Reflexive: the length-0 walk joins v to itself. Symmetric: reverse the path. Transitive: concatenate two walks and extract a path by the theorem above.
By “Equivalence Relations and Partitions” in Sets, Relations, and Functions the classes partition V, and each class induces a maximal connected subgraph.
□
Theorem · The edge bound
A connected graph on n vertices has at least n − 1 edges.
Start with n vertices and no edges: n components. Adding one edge reduces the number of components by at most 1, since it can merge at most two.
To reach one component from n, at least n − 1 edges are required.
□
“Trees” shows that n − 1 edges suffice exactly when the graph is a tree, so trees are the minimally connected graphs — connected, and no edge to spare.
Weak points
Definition · Cut vertex and bridge
A cut vertex is a vertex whose removal increases the number of components. A bridge is an edge whose removal does so.
Theorem · Bridges and cycles
An edge is a bridge if and only if it lies on no cycle.
If e = uv lies on a cycle, removing it leaves the rest of that cycle as a u–v path, so nothing is disconnected.
If e is on no cycle and removing it left u and v connected, that path together with e would form a cycle — a contradiction.
□
So bridges are exactly the edges with no alternative route, which is why network designers avoid them: a bridge is a single point of failure with no redundancy. In a tree, every edge is a bridge.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Analysing connectivity
Search from one vertex; repeat for what is left.
1
Search from any vertex
Breadth-first or depth-first (“Breadth-First and Depth-First Search”). What you reach is its component.
2
Repeat from an unvisited vertex
Until every vertex is assigned. The number of searches is the number of components.
3
Find bridges by removal
Remove an edge and re-count components. An edge on no cycle is a bridge, which is the faster test once cycles are visible.
4
Check the edge count
Fewer than n − 1 edges guarantees disconnection. More does not guarantee connection.
Connectivity
Score 0 / 0Choose the answer you can justify.
Reading a graph's structure
Seven vertices; edges 1–2, 2–3, 3–1, 3–4, 5–6.
Search from 1: 1 → 2 → 3 → 4 component {1,2,3,4}
Search from 5: 5 → 6 component {5,6}
Vertex 7 unvisited component {7}
3 components, |E| = 5, n = 7
n − 1 = 6 > 5, so disconnection was guaranteed in advance.
CUT VERTEX 3 — removing it separates 4 from {1,2}
BRIDGES 3–4 (on no cycle), 5–6 (on no cycle)
1–2, 2–3, 3–1 are NOT bridges: they lie on the
triangle 1–2–3.
The edge count settled the connectivity question before any search: five edges cannot connect seven vertices. That check is free and it is worth doing first.
Common mistakes
1
Using "path" for any routeIn this course a path repeats no vertex. Several theorems — including the bridge characterisation — depend on the distinction.
2
Assuming enough edges implies connectivityn − 1 edges is necessary and not sufficient: a triangle plus two isolated vertices has enough edges and three components.
3
Confusing cut vertices with bridgesOne is a vertex and the other an edge, and neither implies the other. A vertex may be a cut vertex with no bridge incident to it.
Check your understanding
✓
Finish when you can find the components and the bridges by hand.
Take a graph on eight vertices with ten edges, identify its components, and list its bridges by checking which edges lie on no cycle. Both are one search each.
Note: Higher connectivity — how many vertices or edges must be removed to disconnect a graph — is measured by the connectivity κ(G) and edge connectivity λ(G), and Menger's theorem relates them to the number of disjoint paths between vertices. It is the natural sequel to this lesson.