Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in G being broken into two or more components, which are not connected with each other. The size of a cut is called its cardinality. A min-cut of G is a cut in G of minimum cardinality. Consider the following graph on vertices A, B, C, D, E, F with edges A-E, A-B, A-D, A-F, E-D, E-F, B-D, B-C, C-F, D-F. a. Which of the following sets of edges is a cut? i. {(A,B),(E,F),(B,D),(A,E),(A,D)} ii. {(B,D),(C,F),(A,B)} b. What is cardinality of min-cut in this graph? c. Prove that if a connected undirected graph G with n vertices has a min-cut of cardinality k, then G has at least (n*k)/2 edges.

GATE 1999 · Discrete Mathematics · Graph Connectivity · medium

Answer: a. (i) is not a cut, (ii) is a cut. b. min-cut cardinality = 2. c. deg(v) >= k for all v and 2|E| = sum deg(v) >= n*k, so |E| >= (n*k)/2.

  1. Part a: test the two sets: Remove set (i) {A-B, E-F, B-D, A-E, A-D}: the remaining edges A-F, E-D, B-C, C-F, D-F still connect all six vertices (A-F-C-B, A-F-D-E), so the graph stays connected and (i) is NOT a cut. Remove set (ii) {B-D, C-F, A-B}: now B's only remaining edge is B-C, so {B, C} forms its own component while {A, D, E, F} stays connected. Removal disconnects G, so (ii) IS a cut.
  2. Part b: find the min-cut: The smallest degree is deg(C) = 2 (C touches only B and F). The two edges at C, {B-C, C-F}, are a cut that isolates C, giving a cut of size 2, so lambda(G) <= 2. No single edge is a bridge (every edge lies on a cycle, e.g. B-C-F-A-B), so lambda(G) >= 2. Hence the min-cut cardinality is exactly 2.
  3. Part c: every degree is at least k: For any vertex v, the set of edges incident to v is itself a cut (removing them isolates v from the connected graph on n >= 2 vertices). That cut has cardinality deg(v), and the min-cut is the smallest cut, so deg(v) >= k for every v.
  4. Part c: apply the handshaking lemma: Summing deg(v) >= k over all n vertices gives sum of degrees >= n*k. By the handshaking lemma the degree sum equals 2|E|, so 2|E| >= n*k, i.e. |E| >= (n*k)/2. This proves the required bound.