33 votes 33 votes 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: 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\}$ What is cardinality of min-cut in this graph? 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. Graph Theory gate1999 graph-theory graph-connectivity normal descriptive proof + – Kathleen asked Sep 23, 2014 edited May 10, 2019 by Sukanya Das Kathleen 6.3k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply iwasifirshad commented Jun 8, 2020 reply Follow Share @Akash Kanase I have a doubt! Here, in a-i) How it is not a cut set?, since we are getting 2 components, 1. Isolated vertex C 2. Connected edges of {(A,B),(E,F),(B,D),(A,E),(A,D)} so C is isolated from the original graph, so it is 2 components! Please correct me, if I'm wrong! 0 votes 0 votes akshay7797 commented Jun 10, 2020 reply Follow Share @iwasifirshad we won't get isolated vertex C. We are not removing edges (B,C) and (C,F) in (a)-i. Only if those two edges are removed, vertex C becomes isolated. 0 votes 0 votes Abhrajyoti00 commented Jul 23, 2022 reply Follow Share For a) i. The graph after removing the edges $\left\{(A, B), (E, F), (B, D), (A, E), (A, D)\right\}$ will be:- We can see that it’s still connected, rather it’s a spanning tree because it has $5$ edges for $6$ vertices and it’s a connected acyclic graph. 2 votes 2 votes Argharupa Adhikary commented Jul 24, 2022 reply Follow Share Agreed ☺ 0 votes 0 votes Please log in or register to add a comment.
–4 votes –4 votes (a) (i) Not a cut. (ii) It is a cut. (b) 3. {(B,D),(C,F),(A,B)} and {(A,E),(D,E),(E,F)} and {(B,D),(B,C),(A,B)}. Cardinality of each cut set is 3. Rajarshi Sarkar answered Jun 23, 2015 Rajarshi Sarkar comment Share Follow See all 2 Comments See all 2 2 Comments reply Akash Kanase commented Nov 20, 2015 reply Follow Share (a)-> ii is wrong as well as (b) is wrong. 1 votes 1 votes Warrior commented Oct 20, 2017 reply Follow Share (a)-> (ii) is correct but (b) is wrong. 1 votes 1 votes Please log in or register to add a comment.