Graph G is connected if there is a path between every pair of vertices. We call

Question

Graph G is connected if there is a path between every pair of vertices. We call G a tree if it is connected and does not contain a cycle.

Theorem: Let T be a tree on n vertices. Then T has n - 1 edges.

Lemma: 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 bt deleting e contains precisely two conponents.

Prove the theorem by using mathermatical induction and make use of the lemma which you can assume it is correct and do not have to prove.

Explanation / Answer

We can prove the theorem by making use of mathematical induction and also making use of the lemma provided in the question, assuming it to be true.

Theorem: Let T be a tree on n vertices. Then T has n-1 edges.

Proof:

Consider the theorem for number of vertices n=1.

In case the tree T is on 1 vertex, then the theorem says that T has (1-1)=0 edges, which is obviously true.

Therefore, the theorem is true for n=1.

Now on a similar basis, we can say that the result is obviously true for n=1, 2 and 3.

Now proceeding further on similar basis, let us assume that the theorem holds true for all trees having fewer than n vertices.

Now, let there be a tree T having n vertices. Let T have an edge called e.

e is formed by connecting the vertices (components) x and y. This means that the only path between x and y is e.

Therefore, the deletion of e from T will disconnect T.

Now after deletion of e, lets say that T contains exctly two components T1 and T2, and as we did not have any cycles initially, we can still say that T1 and T2, (the two resulting components) are trees (no cycles).

Now, let n1 and n2 be the number of vertices in trees T1 and T2 respectively. Thus, we can say that n1+n2 = n.

Also, we clearly know that n1 < n and n2 < n, since T had a total of n vertices, and T1 and T2 formed when T broke into two components.

Thus by using the mathematical induction hypothesis, the number of edges in T1 will be n1-1 and the number of edges in T2 will be n2-1. (We assumed this result true for number of vertices fewer than n, as proved above in the starting of this answer)

Therefore, the number of edges in T will be = (n1-1) + (n2-1) + 1. [reason: since the theorem says that for n vertices, tree will have n-1 edges, so conversely for n edges, there will be n+1 vertices.]

Which is equal to n1 + n2 - 1.

Which infact equals n-1.

Thus by using mathematical induction and the given lemma, we proved that for n number of vertices,

the tree T has n-1 edges.

Hence proved.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.