This answer is restricted. Please login to view the answer of this question.

Login NowThe 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

- Making schedule on Time table
- Mobile radio Frequency assugnment
- Sudoko
- Register Allocation
- Bipastitle Graph
- Map coloring

**Prove Part:**

“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

**Basic Step:**

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

**Inductive method:**

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

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion