Prove:
If a tree has order 2 or more, then the minimum cut set is 1.
Asked
Active
Viewed 52 times
-1
-
What is $K(G)$? – Sayan Bandyapadhyay May 10 '14 at 23:50
-
I believe $K(G)$ is the connectivity of G. Connectivity being the minimum size of a cut set of G. – Vincent May 11 '14 at 00:04
-
Then why did you say $K_1$ is a counterexample? – Sayan Bandyapadhyay May 11 '14 at 00:07
-
Cut set is a set of edges(not vertices) which disconnects a tree. Thus the claim is true. See my proof. – Sayan Bandyapadhyay May 11 '14 at 00:26
1 Answers
1
Consider any edge $(u,v)$ of a tree. Now we know in a tree there is exactly one path between any two vertices. Consider any path between two vertices through the edge $(u,v)$. If you delete the edge $(u,v)$ then there will not be any path between those two vertices(if $G$ has only two vertices then these two vertices will be $u$ and $v$). Hence those two vertices will lie on different components. Thus the tree is now disconnected. As, deletion of just one edge make the tree disconnected the minimum cut set size is 1 or $K(G)=1$. Hence proved.
-
I checked in http://en.wikipedia.org/wiki/Cut_(graph_theory) it is saying differently. Anyway, don't go with the definition, as long as you have understood the concept you're fine. – Sayan Bandyapadhyay May 11 '14 at 06:25