edge disjoin Cut Set

Question

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.

Answer 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$