Prove that if G is a planar graph of order n
Prove that if G is a planar graph of order n<=11, then G has a vertex of degree 4 or less.
Solution
Suppose G has n vertices and m edges and assume that the degree
of each vertex is greater than or equal to 5. and the
Hand-Shaking Theorem,
5n X
uV (G)
dG(u) = 2|E(G)| 6n 12 n 12.
