26810 Planar Graphs10.4.3 A 3-polytope is the convex hull of a set of points in R3 which do not lieon a common plane. Show that the polyhedral graph of such a polytope is simple.planar,and 3-connected.(Steinitz (1922) proved that, conversely, every simple 3-conncted planar graph isthe polyhedral graph of some 3-polytope.)10.4.4 Show that any 3-connected cubic plane graph on n vertices, where n >may be obtained from one on n -- 2 vertices by subdividing two edges in theboundary of a face and joining the resulting new vertices by an edge subdividingthe face.10.4.5 Arooting ofa plane graph Gis atriple (,,f), where is a vertex, calederte, e is an edge of G incident with v, called the root edge, and f is ao0face incident with e, called the root face.a) Show that the only automorphism of a simple 3-connected plane graph whichixes a given rooting is the identity automorphismb) Let G be a simple 3-connected planar graph. Deduce from (a) that:)aut(G)divides4m,i) aut(G) = 4m if and only if G is one of the five platonic graphs(F.HARARY AND W.T. TUTTE; L. WEINBERG)10.5 Kuratowski's TheoremPlanarity being such a fundamental property, the problem of deciding whether agiven graph is planar is clearly of great inortance. A major step towards this goalis provided by thefollowing characterization of planar graphs, due to Kuratowski(1930).Theorem10.30KURATOWSKI'STHEOREMA graph is planar if and only if it contains no subdivision of either K, or K3.3A subdivision of Ks or K3.3 is consequently called a Kuratouski subdivisionWe first present a proof of Kuratowski's Theorem due to Thomassen (1981)and then explain how it gives rise to a polynomial-time decision algorithm forplanarity.Beforeprovingthetheorem,wereformulateitintermsofminorsMINORSA minor of a graph G is any graph obtainable from G by means of a sequence ofvertex and edge deletions and edge contractions.Alternatively,consider apartition(Vo, Vi,..., Ve) of V such that G[V] is connected, 1 < i < k, and let H be thegraph obtained from G by deleting Vo and shrinking each induced subgraph G[V],<i≤ k, to a single vertex. Then aly spanning subgraph F of H is a nG.For instance, K,is aminor of the Petersen graph because it can be obtainedby contracting the five 'spoke' edges of the latter graph (see Figure 10.19).268 10 Planar Graphs 10.4.3 A 3-polytope is the convex hull of a set of points in R3 which do not lie on a common plane. Show that the polyhedral graph of such a polytope is simple, planar, and 3-connected. (Steinitz (1922) proved that, conversely, every simple 3-connected planar graph is the polyhedral graph of some 3-polytope.) 10.4.4 Show that any 3-connected cubic plane graph on n vertices, where n ≥ 6, may be obtained from one on n − 2 vertices by subdividing two edges in the boundary of a face and joining the resulting new vertices by an edge subdividing the face. 10.4.5 A rooting of a plane graph G is a triple (v,e,f), where v is a vertex, called the root vertex, e is an edge of G incident with v, called the root edge, and f is a face incident with e, called the root face. a) Show that the only automorphism of a simple 3-connected plane graph which fixes a given rooting is the identity automorphism. b) Let G be a simple 3-connected planar graph. Deduce from (a) that: i) aut(G) divides 4m, ii) aut(G)=4m if and only if G is one of the five platonic graphs. (F. Harary and W.T. Tutte; L. Weinberg) 10.5 Kuratowski’s Theorem Planarity being such a fundamental property, the problem of deciding whether a given graph is planar is clearly of great importance. A major step towards this goal is provided by the following characterization of planar graphs, due to Kuratowski (1930). Theorem 10.30 Kuratowski’s Theorem A graph is planar if and only if it contains no subdivision of either K5 or K3,3. A subdivision of K5 or K3,3 is consequently called a Kuratowski subdivision. We first present a proof of Kuratowski’s Theorem due to Thomassen (1981), and then explain how it gives rise to a polynomial-time decision algorithm for planarity. Before proving the theorem, we reformulate it in terms of minors. Minors A minor of a graph G is any graph obtainable from G by means of a sequence of vertex and edge deletions and edge contractions. Alternatively, consider a partition (V0,V1,...,Vk) of V such that G[Vi] is connected, 1 ≤ i ≤ k, and let H be the graph obtained from G by deleting V0 and shrinking each induced subgraph G[Vi], 1 ≤ i ≤ k, to a single vertex. Then any spanning subgraph F of H is a minor of G. For instance, K5 is a minor of the Petersen graph because it can be obtained by contracting the five ‘spoke’ edges of the latter graph (see Figure 10.19)