1314 thank you very much Let T V E be a tree Prove that for

13,14

thank you very much

Let T = (V, E) be a tree. Prove that for any two distinct vertices v, u epsilon V there is a unique path connecting them. Let T = (V, E) be a tree. Prove that |V| = |E| + 1.

Solution

13)

let T = ( V,E) be a tree. Then T is connected, there is at least one path between every pair of vertices in T.

Let there be two distinct paths between two vertices u and v of T. The union of these two paths contains a cycle which contradicts the fact that T is a tree.Hence there is exactly one path between every pair of vertices of a tree.

14)

let T = ( V,E) be a tree and let I V I = n denotes the number of vertices and I E I denotes the number of edges.

We prove the result by using induction on n , the number of vertices. The result is obviously true for n = 1.

Let the result be true for all trees with fewer than n vertices . Let T be a tree with n vertices and let e be an edge with end vertices u and v . So the only path between T₁ and T₂ say and as there were no cycles to begin with, each component is a tree. Let n₁ and n₂ be the number of vertices in T₁ and T₂ respectively, so that n₁ + n₂ = n. Also n₁ < n and n₂ < n.

Thus, by induction hypothesis, number of edges in T₁ and T₂ are respectively n₁ - 1and n₂ - 1.

Hence the number of edges in T = n₁ - 1+ n₂ - 1 + 1 = n₁ + n₂ - 1 = n - 1