prove that a graph G=(V,E) where | v | =n there are at most n-1 edge disjoint cut sets.
I was thinking that for tree it is true since each edge is cut set. but i have no idea how to prove above statement.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Hint:
Let $e \in E$ be arbitrary edge, consider two cases:
- $\{e\}$ is a cut-set, we can not remove that edge, because we could possibly decrease the number of disjoint cut-sets.
- $\{e\}$ is not a cut-set and we can remove it, we won't decrease the number of disjoint cut-sets (you need to argue why).
What is left after we have removed all the edges we could?
I hope this helps $\ddot\smile$
-
$\begingroup$ Thanks for hint. We can use following argument to prove above statement if we use the fact that each spanning tree of a graph contain at-least one edge of all possible cut sets of the graph. Since cut sets are edge disjoint that's why we can have at most n-1 edge disjoint cut sets. [each edge of spanning tree will represent one cut set]. $\endgroup$– RamanujSep 19, 2013 at 2:13