Graph theory Corollary 2 attached below If G is a connected planar simple graph,
ID: 3110510 • Letter: G
Question
Graph theory Corollary 2 attached below If G is a connected planar simple graph, then G has a vertex of degree not exceeding five. If G is a connected planar simple graph, then G has a vertex of degree not exceeding five. Show that every planar graph G (no intersecting edges) can be colored using six or fewer colors. [Hint: Use mathematical induction on the number of vertices of the graph. Apply Corollary 2 of section 10.7 to find a vertex v with deg (v) 5. Consider the subgraph of G obtained by deleting v and all edges incident with it.
Explanation / Answer
to show that every planer graph G can be colored using six colors or fewer colors.
We prove this using mathematical induction on number of vertices of G .
Step 1) Let G be a planar graph suh that number of vertices less than 6
i.e
we colord each vertex by less than of equal to 6 different colors .
therfore reult is true for number of vertex less than 6 .
INDUCTION HYPOTHESIS :-Assume that G be planar graph on vertex V=K can be colored with 6 colors
Let G be planar graph on V=K+1 vertices
[ Corollary:- If G be planar graph then G must have some vertex of degree less than or equal to 5 ]
By corollary
G must have some vertex w of degree less than or equal to 5
We remove vertex w from G
we get new graph G" of vertices V=K
By induction hypothesis
G" can be colored in 6 colores
we think of this as coloring of G except vertex w
But w has degree at most 5
therfore one of six colored not used for any neighbous of w and we can finish coloring of G .
therfore G can be colored using six colored .
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.