Trees. Let G be a graph. Then G is connected if there is a path between every pa
ID: 3842115 • Letter: T
Question
Trees. Let G be a graph. Then G is connected if there is a path between every pair of vertices in G. We call G a tree if it is connected and does not contain a cycle. Prove the following theorem by using mathematical induction. Theorem 1. Let T be a tree on n vertices. Then T has n - 1 edges. In your proof, you may want to make use of the following lemma which you can assume to be correct and do not have to prove. Lemma 2. Let G be a connected graph, and let e be an edge in G that is not contained in any cycle. Then, the graph obtained from G by deleting e contains precisely two components.Explanation / Answer
1)
Let us assume that statement is true for all trees having less than n vertices.
Assume tree with n vertices and ek is edge in Tree T whose end vertices are vi, vj.
So two vertices are connected each other by this edge ek. So by removing ek, the graphs
will disconnect. So that Y-ek have exactly two components.
This happens since there is no circuits in T. Here there will be no cycles in T1 and T2 too..
So V(T1) V(T2) = V(T)
So it is clear that |V(T1)| = |V(T1|-1) and |E(T2)| = |VF(T2)|-1
---------------------------------------------------------------------------------------------
2)
Assume tree with n vertices and ek is edge in Tree T whose end vertices are vi, vj.
So two vertices are connected each other by this edge ek. So by removing ek, the graphs
will disconnect. So that Y-ek have exactly two components.
This happens since there is no circuits in T. Here there will be no cycles in T1 and T2 too.