Q5

MCQMarks unknown

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:

(A)

Which of the following sets of edges is a cut? $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$ $\left\{(B, D), (C, F), (A, B)\right\}$

(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 $\left(\frac{n\times k}{2}\right)$ edges.

Loading…