Chapter 10: Q40E (page 735)
Show that every planar graph \(G\) can be colored using six or fewer colors.
Every planar graph \(G\) can be colored using six or fewer colors.
Over 22 million students worldwide already upgrade their learning with Vaia!
All the tools & learning materials you need for study success - in one app.
Get started for free
Show that \(g\left( 6 \right) = 2\) by first using exercises \(42\) and \(43\) as well as lemma \(1\) in section \(5.2\) to show that \(g\left( 6 \right) \le 2\) and then find a simple hexagon for which two guards are needed.
Find the chromatic number of the given graph.
Find the edge chromatic number of each of the graphs in
Exercises \(5 - 11\) .
The distance between two distinct vertices\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\)of a connected simple graph is the length (number of edges) of the shortest path between\({{\bf{v}}_{\bf{1}}}\)and\({{\bf{v}}_{\bf{2}}}\). The radius of a graph is the minimum over all vertices\({\bf{v}}\)of the maximum distance from\({\bf{v}}\)to another vertex. The diameter of a graph is the maximum distance between two distinct vertices. Find the radius and diameter of
a)\({{\bf{K}}_{\bf{6}}}\)
b)\({{\bf{K}}_{{\bf{4,5}}}}\)
c)\({{\bf{Q}}_{\bf{3}}}\)
d)\({{\bf{C}}_{\bf{6}}}\)
Suppose that a connected graph \(G\) has \(n\) vertices and vertex connectivity \(\kappa \left( G \right) = k\). Show that \(G\) must have at least \(\left\lceil {\frac{{kn}}{2}} \right\rceil \) edges.
What do you think about this solution?
We value your feedback to improve our textbook solutions.
