Cut Set and Connectivity MCQs: 12 Solved Questions on Edge and Vertex Connectivity

Cut-set MCQs look definitional, but the options keep switching between removing vertices, removing edges, counting components and asking what a graph with a given n and m must guarantee. These 12 questions run from cut vertices and bridges to kappa(G) <= lambda(G) <= delta(G) and extremal edge counts, and seven are previous-year: four GATE CS, plus UPPSC Polytechnic Lecturer, Coal India and TCS. Commit to an option and write one reason before reading the explanation. Six answers link that question's own solution page; more previous-year practice sits on the Cut Set and Connectivity PYQ questions hub. The wider syllabus sits in GATE CS Exam Preparation.

Cut sets, cut vertices and connectivity: five facts to use

• Edge cut: a set of edges whose deletion disconnects the graph. A bridge, also called a cut edge, is a one-edge cut.

• Vertex cut: a set of vertices whose deletion disconnects the graph. An articulation point, also called a cut vertex, is a one-vertex cut.

• "Cut-set" is ambiguous: many textbooks reserve it for an edge cut, which is the sense Question 2 tests. Delete edges, keep every vertex, count components.

• Whitney's inequality: kappa(G) <= lambda(G) <= delta(G) for any connected simple graph. kappa is vertex connectivity, lambda is edge connectivity, delta is the minimum degree.

• Densest disconnected graph: on n vertices it is K_(n-1) plus one isolated vertex, carrying (n-1)(n-2)/2 edges. One edge more forces connectivity.

Check all five on a small graph. Take V = {A, B, C, D, E, F} with E = {AB, BC, CA, CD, DE, EF, FD}, triangle ABC and triangle DEF joined only by CD. Deleting CD separates them, so lambda(G)=1. Deleting C or D does too, so kappa(G)=1. The degrees are 2, 2, 3, 3, 2, 2, so delta(G)=2. That reads 1 = kappa(G) = lambda(G) <= delta(G) = 2: the three need not agree even in a connected graph.

MCQs 1-3: definitions and the connectivity inequality

Question 1 (Coal India 2020)

______ of graph is a vertex whose removal disconnects graph.

• A. Start vertex

• B. Middle point

• C. Terminal Vertex

• D. Articulation point / Cut vertex

Correct answer: D. Articulation point / Cut vertex.

The operation is removing one vertex, and a vertex whose removal disconnects what is left is an articulation point, also called a cut vertex. A bridge is the edge counterpart. Full working: cut set and connectivity PYQ page.

Question 2

A cut-set in a graph is:

• A. A set of vertices that disconnects the graph

• B. A set of edges that disconnects the graph

• C. A set of vertices that connects the graph

• D. A set of edges that connects the graph

Correct answer: B. A set of edges that disconnects the graph.

Remove the edge set, keep every vertex: if the component count goes up, that edge set is a cut-set. Option A describes a vertex cut, and C and D invert the test.

Question 3

Let G be a connected simple graph. If κ(G) is the connectivity of the graph, λ(G) is the edge-connectivity of G and δ(G) is the smallest vertex-degree in G, then choose the correct order.

• A. K(G) ≤ λ(G) ≤ δ(G)

• B. λ(G) ≤ K(G) ≤ δ(G)

• C. δ(G) ≤ λ(G) ≤ K(G)

• D. δ(G) ≤ K(G) ≤ λ(G)

Correct answer: A. K(G) ≤ λ(G) ≤ δ(G).

The options write K(G) for kappa(G). Deleting every edge at a minimum-degree vertex isolates it, so lambda(G) <= delta(G). Keeping one endpoint of each edge in a smallest edge cut gives at most lambda(G) vertices that also break the graph apart, so kappa(G) <= lambda(G); in a complete graph all three equal n-1.

MCQs 4-6: articulation points and vertex connectivity in drawn graphs

Question 4 (GATE CS 1999)

The number of articulation point of the following graph is:

• A. 0

• B. 1

• C. 2

• D. 3

Correct answer: D. 3.

The graph is triangle 1-2-3-1, leaf 4 at 2, edge 3-5, and leaves 6 and 7 at 5. Deleting 2 isolates 4, deleting 3 splits the triangle from the 5-6-7 group, deleting 5 separates 6 from 7. No other vertex qualifies, so the count is 3. Full working: cut set and connectivity PYQ page.

Question 5 (UPPSC Polytechnic Lecturer 2018)

In the given graph, identify the cut vertices.

• A. B and E

• B. C and D

• C. A and E

• D. C and B

Correct answer: D. C and B.

A, B and D form a triangle, B joins C, and C joins the leaf E. Removing B leaves A-D on one side and C-E on the other; removing C isolates E. Removing A, D or E keeps it connected, so the cut vertices are B and C. Full working: cut set and connectivity PYQ page.

Question 6 (TCS 2024)

For the given graph (G), which of the following statements is true?

• A. G is a complete graph

• B. G is not a connected graph

• C. The vertex connectivity of the graph is 2

• D. The edge connectivity of the graph is 1

Correct answer: C. The vertex connectivity of the graph is 2.

The edges are AB, AC, BD, BE, CD and CE. Deleting any one vertex leaves the rest connected, and deleting B and C isolates A, D and E, so kappa(G)=2. AD, AE, BC and DE are absent and a path still joins every pair, so A and B are out. Every edge lies on a cycle, so lambda(G)=2, not 1.

MCQs 7-9: bridges, graph unions and component bounds

Question 7 (GATE CS 2015, Set 2)

In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?

• A. A tree has no bridges

• B. A bridge cannot be part of a simple cycle

• C. Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a graph)

• D. A graph with bridges cannot have a cycle

Correct answer: B. A bridge cannot be part of a simple cycle.

The rest of a cycle supplies a second route between an edge's endpoints, so it is no bridge. Every tree edge is a bridge, clique edges lie on triangles, and one graph can carry both a cycle and a bridge. Full working: cut set and connectivity PYQ page.

Question 8 (GATE CS 2004)

Let G1 = (V, E1) and G2 = (V, E2) be connected graphs on the same vertex set V with more than two vertices. If G1 ∩ G2 = (V, E1 ∩ E2) is not a connected graph, then the graph G1 U G2 = (V, E1 U E2)

• A. cannot have a cut vertex

• B. must have a cycle

• C. must have a cut-edge (bridge)

• D. has chromatic number strictly greater than those of G1 and G2

Correct answer: B. must have a cycle.

Assume the union has no cycle. It is connected, so it is a tree. A connected spanning subgraph of a tree keeps every tree edge, forcing both G1 and G2 to be that same tree, whose intersection is connected. That contradicts the premise. Full working: cut set and connectivity PYQ page.

Question 9 (GATE CS 2003)

Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between

• A. k and n

• B. k - 1 and k + 1

• C. k - 1 and n - 1

• D. k + 1 and n - k

Correct answer: C. k - 1 and n - 1.

Deleting an isolated vertex drops the count to k-1, ruling out floors of k (A) and k+1 (D). Only n-1 vertices remain, so the count cannot exceed n-1. A cut vertex can split off several components at once, breaking B's k+1 ceiling. Full working: cut set and connectivity PYQ page.

MCQs 10-12: edge counts that force connectivity or disconnection

Question 10

Consider a simple graph G with 6 vertices. Even though G could have as many as 10 edges and still be disconnected, what is the minimum number of edges required to guarantee that G is connected?

• A. 5

• B. 6

• C. 4

• D. None of these

Correct answer: D. None of these.

The densest disconnected simple graph on six vertices is K5 plus an isolated vertex: C(5,2) = 5 x 4 / 2 = 10 edges. So 11 edges force connectivity and 11 is not listed; four, five and six all fit inside a disconnected graph, since K4 plus two isolated vertices already reaches six.

Question 11

If any simple graph with 20 vertices is necessarily connected, then minimum number of edges needed in G is

• A. 172

• B. 20

• C. 190

• D. 19

Correct answer: A. 172.

The densest disconnected simple graph on twenty vertices is K19 plus an isolated vertex: C(19,2) = 19 x 18 / 2 = 171 edges. One more, 172, forces connectivity. Nineteen edges (D) can form a spanning tree but equally a triangle plus fragments, and 190 (C) is C(20,2), the complete graph.

Question 12

G is an undirected graph with 8 vertices and 12 edges. Find the minimum number of edges whose deletion from G will always guarantee that it will become disconnected.

• A. 5

• B. 6

• C. 7

• D. 8

Correct answer: B. 6.

A connected graph on eight vertices needs at least 8-1=7 edges. Deleting six leaves 12-6=6, under that floor, so disconnection is certain. Deleting five leaves 7, which could still be a spanning tree. Seven and eight deletions also work but are not the minimum.

The traps these questions are designed to trigger

Questions 10 and 11 contrast a possible n-1 edge tree with the higher guarantee threshold. Question 12 reverses it after deletion. In drawings, remove the candidate and recount components. A bridge cannot lie on a cycle; an articulation point may.

The short version and the next practice step

• bridge = one-edge cut

• articulation point = one-vertex cut

• kappa <= lambda <= delta

• Maximum edges in a disconnected n-vertex simple graph: C(n-1,2)

Redo Questions 3, 6, 8 and 11 for the inequality, a two-vertex cut, contradiction and an extremal count. Next use Graph Theory MCQs, Graph Theory for GATE CS, then Discrete Mathematics MCQs for subject-wide practice.

For the full Discrete Mathematics sequence and topic-wise PYQs, continue with GATE Guidance by Sanchit Sir.