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?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
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.