10 Planar Graphs260Proof Let G be a planar embedding of a planar graph G. By Euler's Formula(10.2),wehavef(G) = e(G) - v(G) + 2 = e(G) - D(G) + 2Thus the number of faces of G depends only on the graph G, and not on itsembeddingCorollary 10.21Let G be asimple planar graph on at least three vertices.Thenm < 3n - 6. Furthermore, m = 3n -6 if and only if every planar embedding of Gis a triangulation.Proof It clearly suffices to prove the corollary for connected graphs. Let G be asimple connected planar graph with n ≥ 3. Consider any planar embedding G ofG. Because G is simple and connected, on at least three vertices, d(f)≥3for allf F(G).Therefore, by Theorem 10.10 and Euler's Formula (10.2)1(10.3)2m=)d(f) ≥3f(G) = 3(m-n + 2)fEF(G)or, equivalently.(10.4)m≤3n-6Equality holds in (10.4) if and only if it holds in (10.3), that is, if and only ifd(f) = 3 for each f e F(G).口Corollary 10.22 Every simple planar graph has a verter of degree at most fiveProof This is trivial for n < 3. If n ≥ 3, then by Theorem 1.1 and Corollary 10.21.8n≤d()=2m≤6n-12UEVIt follows that 8≤ 5.口We have already seen that Ks and Ks.3 are nonplanar (Theorem 10.2 andExercise 10.1.1b). Here, we derive these two basic facts from Euler's Formula (10.2)Corollary 10.23 Ks is nonplanar.Proof If Ks were planar, Corollary 10.21 would give10 =e(Ks)≤3u(Ks) -6= 9口Thus Ks must be nonplanarCorollary 10.24 K3.3 is nonplanar260 10 Planar Graphs Proof Let G be a planar embedding of a planar graph G. By Euler’s Formula (10.2), we have f(G) = e(G) − v(G)+2= e(G) − v(G)+2 Thus the number of faces of G depends only on the graph G, and not on its embedding.
Corollary 10.21 Let G be a simple planar graph on at least three vertices. Then m ≤ 3n − 6. Furthermore, m = 3n − 6 if and only if every planar embedding of G is a triangulation. Proof It clearly suffices to prove the corollary for connected graphs. Let G be a simple connected planar graph with n ≥ 3. Consider any planar embedding G of G. Because G is simple and connected, on at least three vertices, d(f) ≥ 3 for all f ∈ F(G). Therefore, by Theorem 10.10 and Euler’s Formula (10.2) 2m = f∈F (G) d(f) ≥ 3f(G) = 3(m − n + 2) (10.3) or, equivalently, m ≤ 3n − 6 (10.4) Equality holds in (10.4) if and only if it holds in (10.3), that is, if and only if d(f) = 3 for each f ∈ F(G).
Corollary 10.22 Every simple planar graph has a vertex of degree at most five. Proof This is trivial for n < 3. If n ≥ 3, then by Theorem 1.1 and Corollary 10.21, δn ≤ v∈V d(v)=2m ≤ 6n − 12 It follows that δ ≤ 5.
We have already seen that K5 and K3,3 are nonplanar (Theorem 10.2 and Exercise 10.1.1b). Here, we derive these two basic facts from Euler’s Formula (10.2). Corollary 10.23 K5 is nonplanar. Proof If K5 were planar, Corollary 10.21 would give 10 = e(K5) ≤ 3v(K5) − 6=9 Thus K5 must be nonplanar.
Corollary 10.24 K3,3 is nonplanar.