We
prove this theorem by induction on the number vertices n.
Basic
step: If n =
1, then G contains only one
vertex and no edge. So the number of edges in
G
is
n
–1
= 1 – 1 = 0.
Induction
hypothesis: The statement is true for all
trees with less than ‘n’ vertices. Induction step:
Now
let
us consider a tree with ‘n’ vertices. Let ‘ek ’ be any edge in T
whose
end vertices are vi and v
j.
Since
T
is
a tree, by there is no other path between vI
and v j. So by removing
ek from T , we get a
disconnected
graph.
Furthermore, T - ek consists of
exactly two components (say T 1
and T 2). Since T
is
a tree, there
were
no circuits in T and so there were
no circuits in T 1 and T
2.
Therefore T 1 and T
2
are also trees.
It
is clear that |V (T
1)|
+ |V (T
2)|
= |V (T
)|
where V (T
)
denotes the set of vertices in T .
Also
|V
(T
1)|
and |V (T
2)|
are less than n.
Therefore
by the induction hypothesis, we have
|
E
(T
1)|
= |V (T
1)|
- 1 and | E (T
2)|
= |V (T
2)|
- 1.
| E (T 1)|
= |V (T 1)|
- 1 and | E (T 2)|
= |V (T 2)|
- 1.
No comments:
Post a Comment