Solution to 1. Construct a proof for the five color theorem for every planar graph. - Sikademy
Author Image

Archangel Macsika

1. Construct a proof for the five color theorem for every planar graph.

The Answer to the Question
is below this banner.

Can't find a solution anywhere?


Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

Theorem: Every planar graph with n vertices can be colored using at most 5 colors.

Proof by induction, we induct on n, the number of vertices in a planar graph G.

Base case, P(n≤5): Since there exist ≤5 nodes in G, the graph can be colored using 5 colors.

Inductive step, P(n+1): Assuming P(n)

P(n) is true, that is, every planar graph with n vertices, we need to show P(n)

P(n) is true.

We know every planar graph has one vertex with deg(v)≤5. We call this vertex v in our graph G. Remove v and for the remaining subgraph G′ we can assume P(n).

If deg⁡(v)≤4, we can color all vertices adjacent to v using 4 colors and use color 5 to color v itself to reach a valid coloring.

If deg⁡(v)=5, we assume that all vertices adjacent to v are colored in different colors.

Hence proved.

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3913-qpid-2612