List any two applications of graph coloring theorem. Prove that “A tree with n vertices has n-1 edges”

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

  1. Making schedule on Time table
  2. Mobile radio Frequency assugnment
  3. Sudoko
  4. Register Allocation
  5. Bipastitle Graph
  6. 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.
Leave your Answer:

Click here to submit your answer.

  Loading . . .