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

Updated 29 Oct 20266 min read
Cut Set and Connectivity in Graph Theory: Edge and Vertex Connectivity with Worked Examples

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:

  1. Look for a bridge, which gives lambda(G)=1.

  2. Otherwise use cycles or edge-disjoint paths to rule out a one-edge cut.

  3. 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).

Bow-tie graph in three panels: the original, the split after deleting vertex v, and the same split after cutting edges av and bv.

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.

Two bow-tie diagrams showing paths a-v-c and a-b-v-d-c as edge-disjoint above, and sharing internal vertex v as the separator below.

6. Minimum cuts, minimal cuts, and standard graph values

Graph

delta(G)

lambda(G)

kappa(G)

Exact witness

P_5, edges {12,23,34,45}

1

1

1

Bridge 23; deleting vertex 3 disconnects the path

C_5, edges {12,23,34,45,51}

2

2

2

{12,15} isolates 1; deleting {2,5} isolates 1

K_4

3

3

3

Three edges incident on one vertex; kappa(K_4)=4-1

Bow-tie graph

2

2

1

Edge cut {av,bv}; vertex cut {v}

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 delta(G) as lambda(G)

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 kappa=lambda for every connected graph

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.