This answer is restricted. Please login to view the answer of this question.Login Now
The process o f assigning a color to each vertex of a simple graph so that no two adjacent verticesa re asigned to the same cover is called graph coloring.
Some applications of graph coloring is
“A tree with n vertices has n-1 edge”
Let ‘s prove by mathematical induction
Assume p(n) : Number of edges = n-1 for all tree with n vertices
p(1): For one vertex, there will be zero edges. So, it is true.
p(2): For two vertices, there will be one edge to connect them. so, it is true.
p(3): For three vertices, there should be two edge to connect them. So, it is true
Let us assume for any arbitary k, p(k) is true. i.e. for k no of vertices, no of edges = k -1
Now, for p(k+1)
the no. of edges will be (k-1) + no of edges required to add (k+1)th vertex.
Every vertex that is added to the tree contributes one edge to the tree.
Thus, no of edges required to add (k+1)th node = 1
So, total no of edges will be = (k-1) + 1 = k-1 +1 = k
Thus, p(k+1) is true
So, by using principle of mathematical induction. It is proved that for n vertices, no of edges = n-1
Click here to submit your answer.