Prove or disprove the following:
(a) Every 3-regular planar graph has a 3-coloring.
(b) If ?=(?,?) is a 3-regular graph and there exists a perfect matching of ?, then there exists a set of edges A⊆E such that each component of G′=(V,A) is a cycle
(a) False.
Take G=K4, the complete graph with 4 vertices. This is a 3-regular graph with chromatic number 4. K4has no three coloring.
(b) True.
Get Answers For Free
Most questions answered within 1 hours.