cut-set of a graph

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

radha gogia

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.

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.

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.