Coffee Room
Discuss anything here - everything that you wish to discuss with fellow engineers.
12890 Members
Join this group to post and comment.
radha gogia • Dec 10, 2014

# cut-set of a graph

I just had one confusion regarding cut-set that the definition of cut-set says that it is the minimal set of edges whose removal from a graph disconnects the graph and increases the number of connected components by 1.
Now,the point of confusion lies here that why do we say that the number of connnected components increase by 1,since there can be many edges whose removal can lead to more than 2 disconnected components,so even if we say minimal there can be cases when actually removing some edges would increase the number of connected components more than by 1.

Also,one query regarding the rank of the graph which is calculated as n-k where k are the number of connected components in the graph,so in a graph the number of connected components in a connected graph always remains 1,so why then a usage of the term k.
ManojKiran Eda • Dec 10, 2014
I am also having the same problem...can any one please clear it.