Let G be a connected, undirected graph. A cut in G is a set of edges whose…

PYQ GATE 1999

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.

Undirected graph with vertices A, B, C, D, E and F for the cut questions.

(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 the cardinality of a 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 nk/2 edges.

Attempted by 1 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…