Suppose G is a simple connected graph with 12 vertices and 16 edges. Suppose 4 of its vertices are degree 1, and 3 of its vertices are degree 2. Prove that G is planar. (Hint: Kuratowski)
(b) Suppose G is a simple connected graph with 12 vertices and 16 edges. Suppose 4 of its vertices are degree 1, and 3 of its vertices are degree 2. Prove that G is planar. (Hint: Kuratowski)
(c) Let G be any simple connected planar graph with n vertices and e edges. Suppose there are exactly y vertices of degree 2. Assume that n - y > 3. Prove that e < 3n - y - 6. (Hint: Explain why the degree-2 vertices can be erased, and how to take care of any resulting loops or multiple edges.)
(d) Suppose that a connected simple graph G' has exactly 10 vertices of degree 4, 8 vertices of degree 5, and all other vertices have degree 7. Find the maximum possible number of degree-7 vertices G could have, so that G would still be planar.
Step by step
Solved in 3 steps
