Cut Set and Connectivity in Graph Theory: Edge and Vertex Connectivity with Worked Examples
Learn how to calculate edge and vertex connectivity without confusing cuts, degrees, or disjoint paths. The bow-tie graph shows why lambda(G) can exceed kappa(G).
KnowledgeGate Team
Exam prep & CS education

Deleting an edge and deleting a vertex can break the same graph in different ways, so visually spotting one weak point does not automatically give both connectivity values. Edge cuts, vertex cuts, bridges, articulation vertices, minimum cuts, and minimal cuts differ in what they remove and how they are certified. In the bow-tie graph, the definitions and Menger's theorem yield lambda(G)=2 but kappa(G)=1. Both values require an upper bound and a matching lower bound; minimum degree alone does not determine either.
1. Cut sets and connectivity: what is being removed?
Let G=(V,E) be a finite, simple, connected, undirected graph. For F subseteq E, G-F deletes only the edges in F. For S subseteq V, G-S deletes those vertices and their incident edges. The object removed is the unit counted.
An edge cut disconnects G when deleted. For nonempty proper X subset V, its boundary is delta(X)={xy in E: x in X, y in V-X}. A vertex cut disconnects the remaining graph when deleted, subject to the complete-graph convention below. A one-edge cut is a bridge; a one-vertex cut is an articulation vertex. "Cut set" is the umbrella phrase.
A minimum cut has the smallest cardinality of its type. A minimal cut has no proper subset that is a cut, but can be larger than the minimum. These cut definitions sit within GATE CS Exam Preparation. Graph Theory for GATE CS: Concepts and Worked Examples surveys degrees, walks, trees, colouring, and planarity. Cut-set questions instead ask for the minimum edge or vertex removal that disconnects a graph.
2. Edge connectivity lambda(G): find an upper bound, then prove it is tight
Edge connectivity is
lambda(G)=min{|F|: G-F is disconnected}.
Equivalently, for a connected graph with at least two vertices, it is the minimum |delta(X)| over nonempty proper X subset V. A cut of size r proves only lambda(G) <= r; equality needs proof that fewer edges cannot disconnect the graph.
Use this sequence:
Look for a bridge, which gives
lambda(G)=1.Otherwise use cycles or edge-disjoint paths to rule out a one-edge cut.
Exhibit a small boundary, often at a minimum-degree vertex.
If u has minimum degree, deleting its deg(u)=delta(G) incident edges isolates it. Thus lambda(G) <= delta(G), but equality still needs a matching lower bound. Engineering Mathematics for GATE gives a structured route through the wider discrete-mathematics sequence.
3. Vertex connectivity kappa(G): articulation points and the complete-graph convention
For a connected non-complete graph,
kappa(G)=min{|S|: G-S is disconnected}.
An articulation vertex gives kappa(G)=1. For complete K_n, the standard convention is kappa(K_n)=n-1: fewer deletions leave a connected complete graph, while deleting n-1 vertices leaves the trivial graph.
Delete a likely bottleneck and its incident edges, then count the remaining components. A cut of size r gives an upper bound; equality requires every deletion of r-1 vertices to leave the graph connected. One vertex can remove several edges, so the two connectivity values need not match.
Whitney's inequality gives the essential check for every connected simple graph with at least two vertices:
kappa(G) <= lambda(G) <= delta(G).
It checks consistency, not equality. delta(G)=3 permits lambda(G) <= 3 and kappa(G) <= lambda(G), but determines neither value.
4. Cut set worked example: two triangles sharing one vertex
Take V={a,b,v,c,d} and E={ab,av,bv,vc,vd,cd}: triangles a-b-v-a and v-c-d-v share only v, which gives the bow-tie graph. Here deg(a)=deg(b)=deg(c)=deg(d)=2 and deg(v)=4, so delta(G)=2.
Delete v. Then G-{v} has exactly two components: edge ab on {a,b} and edge cd on {c,d}. Thus kappa(G) <= 1. Since connected G cannot be disconnected by deleting zero vertices, kappa(G)=1.
Every edge lies on a 3-cycle, so deleting one leaves an alternate route and cannot disconnect the graph. Hence lambda(G) >= 2. Delete F={av,bv}: {a,b} remains joined by ab but has no edge to {v,c,d}. Therefore F=delta({a,b}) is a two-edge cut and lambda(G) <= 2.
The bounds match: lambda(G)=2. The full check is 1=kappa(G) <= 2=lambda(G) <= 2=delta(G).

5. Menger's theorem explains why the two connectivity values differ
Menger's edge form equates the minimum number of edges separating distinct x,y with the maximum number of pairwise edge-disjoint x-y paths. For nonadjacent a,c, take:
P1=a-v-c, with edges{av,vc}P2=a-b-v-d-c, with edges{ab,bv,vd,dc}
Their edge sets do not overlap. Since deg(a)=2, at most two edge-disjoint paths leave a; these paths attain 2. Cut {av,bv} separates a from c, so the local minimum edge cut is also 2, agreeing with lambda(G)=2.
For this nonadjacent pair, the vertex form equates the minimum internal-vertex separator with the maximum number of internally vertex-disjoint a-c paths. Every a-c path uses v, so {v} is a one-vertex separator and the maximum is 1, agreeing with kappa(G)=1. The displayed paths are edge-disjoint but share internal vertex v: edge redundancy can coexist with one vertex bottleneck.

6. Minimum cuts, minimal cuts, and standard graph values
Graph |
|
|
| Exact witness |
|---|---|---|---|---|
| 1 | 1 | 1 | Bridge |
| 2 | 2 | 2 |
|
| 3 | 3 | 3 | Three edges incident on one vertex; |
Bow-tie graph | 2 | 2 | 1 | Edge cut |
No single edge or vertex deletion disconnects C_5. For K_4, use the complete-graph convention.
A second graph separates minimal from minimum. Let H have V(H)={A,B,C,D} and E(H)={AB,BC,CD,DA,AC}, a square plus diagonal AC. Cut delta({A})={AB,AD,AC} is minimal: restoring any one edge reconnects A to connected {B,C,D}. Yet delta({B})={AB,BC} isolates B. Every edge lies on a cycle, so no one-edge cut exists and lambda(H)=2. The size-3 cut is inclusion-minimal but not minimum.
Deleting any one vertex of H leaves a connected path or triangle, while deleting {A,C} leaves nonadjacent B,D. Thus kappa(H)=2, and kappa(H)=lambda(H)=delta(H)=2.
7. How cut sets and connectivity are tested, plus traps to avoid
Representative questions ask you to identify bridges or articulation vertices, calculate both connectivities, distinguish minimum from minimal cuts, apply Whitney's inequality, count disjoint paths, or track one changed edge.
Mistake | Why it fails | Exact repair |
|---|---|---|
Reporting | Minimum degree gives only an upper bound | Exhibit the cut and prove no smaller cut works |
Counting incident edges after deleting a vertex | One vertex removal may erase many edges | Count removed vertices, not erased edges |
Treating every minimal cut as minimum | Inclusion and cardinality are different | Compare its size with all smaller possible cuts |
Calling paths vertex-disjoint when they share an internal vertex | Shared internal vertices violate the definition | List the internal vertices of each path |
Applying Menger's vertex form to adjacent endpoints without a convention | The direct edge creates a special case | Use a nonadjacent pair or state the required convention |
Assuming | The bow-tie graph has values 1 and 2 | Calculate each type from its own definition |
Rapid checks: P_5 has both values 1. C_5 has both values 2. In the bow-tie graph, removing v gives kappa=1, but no edge is a bridge, so lambda=2. Given only delta(G)=3, exact values remain undetermined. Continue with Graph Theory MCQs: 12 Solved Euler, Coloring, Trees for follow-on practice.
8. Cut set and connectivity: the short version and next step
Specify whether edges or vertices are deleted.
Exhibit a cut to prove an upper bound.
Prove that a smaller deletion cannot work.
A bridge gives
lambda=1.An articulation vertex gives
kappa=1.Verify
kappa <= lambda <= delta.
For the bow-tie graph, delta=2, lambda=2, and kappa=1. Redraw it from the edge list, delete {av,bv}, delete {v}, and trace both a-c paths. You are done when you can explain why they are edge-disjoint but not internally vertex-disjoint, and why the connectivity values differ.
For a sequenced route that places graph theory within the broader preparation plan, continue with GATE Guidance by Sanchit Sir.
Keep learning
Cut Set and Connectivity MCQs: 12 Solved Questions on Edge and Vertex Connectivity
Solve 12 graph connectivity MCQs, seven of them previous-year, then check each answer against an explanation of cut sets, articulation points and bridges.
Graph Coloring: Vertex Coloring, Edge Coloring, Chromatic Number and Theorem Bounds
Learn to separate vertex coloring from edge coloring, prove exact chromatic values on one six-vertex graph, and apply standard theorem bounds without overclaiming.
Graph Coloring MCQs: 10 Solved Questions on Vertex Coloring, Edge Coloring and Chromatic Number
Attempt 10 solved GATE questions on graph colouring, from bipartite tests to edge colouring. Each solution proves a lower bound, constructs a colouring or traces the relevant algorithm.
Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity
Graph theory for GATE CS: degree and handshaking, Euler vs Hamiltonian paths, planarity and Euler's formula, chromatic number, trees and spanning trees.





