A TREE is a connected graph with no cycles. (a) Use Induction to show: if a tree

Question

A TREE is a connected graph with no cycles.

(a) Use Induction to show: if a tree has n vertices then it has n-1 edges.

(b) (HINT: Taking a tree and adding a vertex is NOT a valid proof
because there could be trees that are NOT constructed in this
manner.)

(c) (HINT: Take a tree with n + 1 vertices and remove something
from it. (You could remove an edge or a vertex.) Then look at
what remains, and apply your inductive hypothesis to these re-
mains, and finally reverse the removal and argue that what you've
found out about the remains implies that the original graph (with
nothing removed) has n edges.)

Explanation / Answer

Statement: A tree G with n vertices has (n-1) edges.

Proof by induction:
--------------------
Step1: consider for n=1
For n=1, graph contains one vertex so there will not be any edges. so number of edges => (n-1) = (1-1) = 0

Step2:
Consider for n=2
As two vertices are there, the number of edges will be one.. which connects both vertices,
So n-1 ==> 2-1 = 1 ...correct

Step3:
So now consider , this statement holds true for n vertices..
Let E be edge in a tree T and correspondence vertices are V1, V2.
As it is tree, there will not be any edge apart from this E .
So now removing edge E from T , we get disconnected Graph...
Then T-E has two components exactly like T1, T2.
As T1, T2 are disconnected there will not be any circuits.
So , straight away we can say T1+T2 = T and also T1 and T2 vertices are less than n.

So by induction E(T1) = v(T1) - 1 and
E(T2) = v(T2) - 1

Hence Proved by mathematical induction.
A tree G with n vertices has (n-1) edges.   

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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