4.2Connectivity: components, bridges, cut vertices
The idea
A graph is connected if there is a path between every two vertices. A bridge is an edge whose removal disconnects it, and a cut vertex is a vertex whose removal does.
Think of it like this: A road network: a bridge is a road whose closure cuts the map in two; a cut vertex is a junction that does the same.
Why it exists
Questions ask for the minimum or maximum number of edges for a given connectivity, and for the number of components.
How it works
- n vertices and e edges: at least n − e components.
- A connected graph needs at least n − 1 edges.
- A graph with more than C(n−1, 2) edges must be connected; C(n−1,2) edges can still leave it disconnected (K_{n−1} plus an isolated vertex).
- Edges on a cycle are never bridges. Vertex connectivity ≤ edge connectivity ≤ minimum degree.
Worked example: Most edges of a disconnected simple graph on 8 vertices
K₇ plus one isolated vertex: C(7, 2) = 21. With 22 edges it must be connected.
Now play with it
- →Load the bowtie: the shared vertex is a cut vertex.
- →Load two triangles and count the components.
Check yourself
The maximum number of edges in a simple disconnected graph on 6 vertices is
Exam notes (the dense version)
A graph with n vertices and e edges has at least n − e components. A connected graph needs at least n−1 edges; a graph with more than C(n−1,2) edges must be connected. A bridge is an edge whose removal disconnects; a cut vertex likewise. Vertex connectivity κ ≤ edge connectivity λ ≤ min degree δ. A graph is 2-connected iff every pair lies on a common cycle.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.