# cut-set of a graph

Question asked by radha gogia in #Coffee Room on Dec 10, 2014

radha gogia · Dec 10, 2014

Member of CrazyEngineers

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. Posted in: #Coffee Room

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. Posted in: #Coffee Room

ManojKiran Eda · Dec 10, 2014

Member of CrazyEngineers

I am also having the same problem...can any one please clear it.

pratap singh, upendra · May 20, 2015

Member of CrazyEngineers

When you try to find the cut set of the graph, you subconsciously focus on one component of the graph and that's what you are supposed to do. Taking this component, you remove one edge and see if this component breaks into two sub-components. Is yes, then the removed edge becomes the cut set. If no, then you remove another edge to see if the component breaks. You continue until component actually breaks. The set of removed edges become the cut set.radha gogiaI 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.

Sometimes you begin at a site(say site 1) and then you realize that starting from this site, it is not possible to define a cut set. Then you switch to some other site(say site 2) and start removing edges around this site. Before you start removing edges from site 2, you have to put all removed edges of site 1 back in their position.

This will ensure that a cut set causes an increase in the number of components by 1 only.

Note that site 1 and site 2 belong to the same component.