This article on GeeksForGeeks provides a really nice proof of the fact that E=V-1 for trees. It uses strong induction on the number of edges. The key idea is to remove an edge, and compute the number of edges separately for the resulting two disconnected trees, and add the removed edge to end up with the result. The converse is easy to prove but is not dealt with properly in the article. Here is a correct proof of the statement "if a Graph G has n vertices and n-1 edges, then it is a tree.":- The lemma used is that any acyclic connected graph is a tree. The proof is trivial (since cyclicity leads to at least two different paths from vertex u to v, which are a part of the cycle). So, consider that the G has cycle(s). Then we can keep on removing edges such that there are no cycles in G and G is still connected. Then G results into a tree. Then the number of edges has decreased, but not the number of vertices. By the previous theorem, we have a contradiction (since now ...
Comments
Post a Comment