Graph connectivity: components and cuts
Objectives, prerequisites and conventions
Reason about connected components, bridges, articulation vertices, trees and spanning forests; distinguish weak from strong connectivity in directed graphs; and interpret small edge/vertex cuts without assuming that degree alone settles connectivity. Prerequisites: graph terms and adjacency representations, basic sets and counting. Existing BFS/DFS lessons teach traversal mechanics; this lesson develops structural arguments instead of repeating their code traces.
Unless a section explicitly says directed, graphs are finite, simple and undirected: no loops or parallel edges. Vertices and edges are labeled. We allow a length-0 path from a vertex to itself and regard the one-vertex graph as connected. Empty-graph conventions are not used in practice questions. A component means a maximal connected vertex set, not the longest path in the graph.
1. Reachability partitions the vertices
An undirected graph is connected when every pair of vertices is joined by a path. Reachability is reflexive (the length-0 path), symmetric (reverse a path) and transitive (combine walks and remove repeated portions to obtain a path). Its equivalence classes are the connected components.
An isolated vertex forms a component of size 1. Two different components have no edge between them; otherwise its endpoints and their components would be connected. If a graph has c components, adding an edge between two different components reduces the count by exactly 1. Adding an edge inside one component does not reduce it.
Therefore at least c−1 new edges are necessary to make the graph connected, and c−1 suffice: choose one representative in each component and connect the representatives as a tree. This is a statement about available new edges between components, not a claim that arbitrary c−1 added edges will work. Repeatedly adding internal edges can leave the graph disconnected.
2. Bridges are critical edges
An edge is a bridge if deleting it, while retaining all vertices, increases the number of connected components. A bridge's deletion increases the count by exactly 1. Removing one edge cannot break its former component into more than two pieces: any former path crossing that edge can be separated into a path to one endpoint and a path from the other.
An edge is a bridge exactly when it lies on no cycle. If an edge is on a cycle, the rest of the cycle provides an alternate route between its endpoints, so removing it does not destroy connectivity between them. Conversely, if removing an edge leaves its endpoints connected, an alternate simple path together with the deleted edge forms a cycle.
This criterion concerns the graph, not its drawing. A long-looking line need not be a bridge, and a crossing of drawn lines is not a vertex unless specified. A bridge can occur even when every vertex has degree at least 2.
3. Worked graph: two triangles joined by one edge
Use V={a,b,c,d,e,f} and E={ab,bc,ca,cd,de,ef,fd}. Edges ab,bc,ca form one triangle; de,ef,fd form another. Edge cd is their only connection.
The graph is connected, with n=6 vertices and m=7 edges. Edge cd is the only bridge. Every other edge lies on one of the triangles, so deleting it leaves an alternate route. Deleting cd gives the two components {a,b,c} and {d,e,f}.
An articulation vertex, or cut vertex, is a vertex whose deletion, together with all incident edges, increases the component count. In this graph c and d are articulation vertices. Deleting c leaves components {a,b} and {d,e,f}; deleting d leaves {a,b,c} and {e,f}. Deleting a leaves the graph connected, since b remains joined through c. Similar reasoning handles the other non-cut vertices.
Degrees are 2,2,3,3,2,2, so minimum degree δ=2. Yet one edge or one vertex can disconnect the graph. Minimum degree 2 does not guarantee resilience to every single-edge or single-vertex failure.
4. Edge deletion and vertex deletion are different tests
When testing a bridge, leave every vertex in place and remove only the edge. When testing an articulation vertex, remove that vertex and every incident edge before recounting components. A large degree alone does not prove articulation, and a degree-2 vertex can be an articulation vertex in a path.
For the path 1−2−3−4, every edge is a bridge, while only vertices 2 and 3 are articulation vertices. Deleting leaf 1 leaves the connected path 2−3−4, so the component count remains 1. For the two-vertex graph with one edge, that edge is a bridge but neither vertex is an articulation vertex: deleting either leaves a single connected vertex.
Definitions also apply to a disconnected graph by comparing component counts before and after deletion. A vertex in one component may be an articulation vertex if it splits that component. Deleting an isolated vertex decreases the component count, so it is not an articulation vertex under this definition.
5. Trees: several equivalent characterizations
A tree is a connected graph with no cycle. For a simple undirected graph with n≥1, the following characterize a tree:
- It is connected and has exactly n−1 edges.
- It is acyclic and has exactly n−1 edges.
- Every pair of distinct vertices has exactly one simple path between them.
A tree has a path between each pair because it is connected. If there were two different simple paths, their divergence and reunion would create a cycle, contradicting acyclicity. Conversely, a cycle gives two distinct simple paths between two of its vertices. This proves the unique-path characterization.
A finite tree has n−1 edges, which can be shown by repeatedly removing a leaf and its incident edge down to a single vertex. A connected graph has a spanning tree: keep removing a cycle edge while preserving connectivity until no cycles remain. This gives at least n−1 edges in a connected graph. If a connected graph already has n−1 edges, no extra edge beyond that tree remains, so it is itself a tree.
Exactly n−1 edges alone does not imply a tree. A triangle plus an isolated vertex has n=4,m=3=n−1 but is disconnected and cyclic. Read the additional connectedness or acyclicity condition.
6. Forests, component counts and surplus edges
A forest is an acyclic graph, possibly disconnected. If it has n vertices and c components, each component is a tree, so the total edge count is Σ(nᵢ−1)=n−c. Isolated vertices fit: their component contributes one vertex and zero edges.
For an arbitrary undirected graph with n vertices, m edges and c components, a spanning forest uses n−c edges: one spanning tree inside each component. Thus m≥n−c, with equality exactly when the graph is already a forest. The number of edges outside a chosen spanning forest is m−n+c.
Each extra edge creates one fundamental cycle with the unique forest path between its endpoints. The number m−n+c is the cycle-space dimension, not the total number of simple cycles. Different cycles may overlap and combine. For our two-triangle graph, m−n+c=7−6+1=2. Removing one edge from each triangle leaves a spanning tree with 5 edges; the bridge cd must remain in every spanning tree.
If a graph has c components, creating a spanning tree of the entire vertex set requires first connecting those components. A spanning forest already exists inside the disconnected graph, but a spanning tree of the entire disconnected graph does not.
7. Small cuts and connectivity parameters
An edge cut is a set of edges whose removal disconnects a connected graph. For a connected graph with at least two vertices, edge connectivity λ is the smallest size of such a set. A bridge means λ=1. A graph without bridges may still disconnect after two edge removals.
Vertex connectivity κ is the minimum number of vertices whose removal disconnects the remaining graph or reduces it to a single vertex. The single-vertex alternative handles complete graphs; with this convention κ(Kₙ)=n−1 for n≥2. For the same graphs λ(Kₙ)=n−1. These conventions should be stated before using formulas for complete graphs.
For the cycle C₄, λ=2: one removed edge leaves a connected path, while two suitable edges disconnect it. Also κ=2: one removed vertex leaves a connected path, while two opposite vertices leave two isolated vertices. In the two-triangle graph, both λ and κ equal 1, despite δ=2. To establish an exact minimum cut size, exhibit a cut of that size and explain why every smaller deletion fails to disconnect; one cut alone provides only an upper bound.
8. Directed graphs: weak is not strong
In a directed graph, a path must follow edge directions. Strong connectivity means every vertex can reach every other by a directed path. Weak connectivity means the undirected graph obtained by ignoring directions is connected. Strong connectivity implies weak connectivity, but not conversely.
With edges a→b and b→c, the graph is weakly connected but not strongly connected: c cannot reach a. Its strongly connected components (SCCs) are {a},{b},{c}. With a→b,b→c,c→a, all three lie in one SCC.
An SCC is a maximal set of mutually reachable vertices. If every SCC is contracted into a single vertex, ignoring internal edges, the resulting directed graph has no directed cycle. A cycle between distinct SCCs would make their vertices mutually reachable and force them to be one SCC. This structural fact does not depend on choosing a particular SCC algorithm.
A reliable audit procedure
State graph conventions and list all edges. Count components before a deletion, perform the exact requested deletion, then count again. For a claimed tree, check both edge count and the accompanying structural condition. For an exact cut value, prove a lower bound and provide a matching cut. For directed questions, keep orientation and weak/strong terminology explicit. Matching, vertex colouring, Menger's theorem and efficient cut-finding algorithms remain further study; this lesson is not complete graph theory.
Original practice: six single-correct MCQs
Original questions, not previous-year questions. Choose exactly one option. Keep all stated index, domain and graph conventions.
C01. Let V={a,b,c,d,e,f}, E={ab,bc,ca,cd,de,ef,fd}. Which is the complete set of bridges?
A. {ab,bc,ca} B. {cd} C. {de,ef,fd} D. Every edge
Answer: B
A: These edges lie on the first triangle and each has an alternate endpoint path.
B: Only cd joins the triangles; removing it creates two components. Every other edge is on a cycle.
C: These edges lie on the second triangle, so none is a bridge.
D: Cycle edges are not bridges; only the joining edge is critical.
C02. For the same two-triangle graph, what is the complete set of articulation vertices?
A. {a,b,e,f} B. {c} C. All six vertices D. {c,d}
Answer: D
A: Deleting any of these leaves its triangle’s other two vertices connected to the rest.
B: d is an articulation vertex as well as c.
C: The other four deletions leave the graph connected.
D: Deleting c separates {a,b} from {d,e,f}; deleting d separates {a,b,c} from {e,f}. No other vertex deletion disconnects it.
C03. A forest has 7 vertices and 3 connected components. How many edges does it have?
A. 4 B. 6 C. 3 D. 10
Answer: A
A: Each component is a tree, so total edges equal n−c=7−3=4.
B: n−1=6 assumes one connected tree, not three components.
C: The component count is not the edge count.
D: n+c is not the forest identity; it would introduce cycles.
C04. Which example disproves the claim that every simple undirected graph with n−1 edges is a tree?
A. A connected path on four vertices B. A triangle plus one isolated vertex C. A connected graph with no cycle D. A one-vertex graph with no edge
Answer: B
A: This is a tree and does not refute the claim.
B: It has n=4,m=3=n−1 but is disconnected and contains a cycle; edge count alone is insufficient.
C: This is exactly the definition of a tree.
D: Under the stated convention this is a tree with n=1,m=0.
C05. For the cycle C₄, what are vertex connectivity κ and edge connectivity λ, respectively, under the stated definitions?
A. 1, 1 B. 1, 2 C. 2, 2 D. 2, 1
Answer: C
A: Neither one edge nor one vertex disconnects a cycle; each leaves a connected path.
B: One vertex deletion leaves a path, so κ is not 1.
C: Any single deletion leaves connectivity; two opposite vertices or two suitable edges disconnect, proving both minima are 2.
D: The cycle has no bridge, so λ is not 1.
C06. A directed graph has exactly the edges a→b and b→c. Which statement is correct?
A. It is strongly connected with one SCC. B. It is neither weakly nor strongly connected. C. It is weakly connected and has two SCCs. D. It is weakly connected, not strongly connected, with three singleton SCCs.
Answer: D
A: c has no path back to a, so mutual reachability of all vertices fails.
B: Ignoring directions gives the connected path a−b−c, so weak connectivity holds.
C: No distinct pair is mutually reachable; none can be grouped into a two-vertex SCC.
D: Ignoring arrows yields a connected path, but reverse reachability is absent; SCCs are {a},{b},{c}.
Sources and scope
This original lesson develops a specified Discrete Mathematics topic from Section 1 of the official GATE 2027 CS syllabus. It is not a declaration that the whole subject or syllabus is complete. The syllabus confirms relevance; the institutional course chapter is a further-study reference. Worked examples, wording and practice are original.
Sources opened and checked 2026-10-14.
Sign in to keep your progress. Sign in