27510.6Surfacmbeddings of Graphsk vertices. The graph obtained from their union G, UG2 by deleting the edges ofGi nG2 is called the k-sum of Gi and G2.a) Show that if Gi and G2 are planar and k = 0,1, or 2, then the k-sum of GandG2isalsoplanab) Express the nonplanar graph K3,3 as a 3-sum of two planar graphs.10.5.11SERIES-PARALLELGRAPHA series ertension of a graph is the subdivision of a link of the graph; a parallelertension is the addition of a new link joining two adjacent vertices. A series.parallel graph is one that can be obtained from K2 by a sequence of series andparallel extensionsa) Show that a series-parallel graph has no Kf-minor.b)By applying Exercise 10.1.5, deduce that a graph has no Ky-minor if and onlyif it can be obtained from Ki, the loop graph L, (a loop incident with a singlevertex), and the family of series-parallel graphs, by means of O-sums, I-sums(G.A. DIRAC)and2-sums10.5.12 Show that agraph is outerplanar if and only ifit has neithera Ka-minornoraK2.3-mino10.5.13 ExCLUDEDK3.3-MINORShowthata) every 3-connected nonplanar graph on six or more vertices has a Kaa-minorb) any graph with no K3.37edfromthefamilyofplanargraphsmTbeobtaand K, by means of O-sums, 1-sums, and 2-sums. (D.W. HALL; K. WAGNER)10.5.14 ExCLUDED Ks-MINORShowthata) the Wagner graph, depicted in Figure 10.23, has no Kg-minor,b)if Gi and G2 aretwo graphs,each of which is either a planar graph or theWagner graph, then no O-sum, 1-sum, 2-sum, or 3-sum of Gi and G2 has aKs-minor(Wagner (1936) showed that every 4-connected nonplanar graph has a Ks-minorand deduced the converse of (b), namely that any graph with no Kg-minor canbe obtained from the family of planar graphs and the Wagner graph by means of0-sums, 1-sums, 2-sums, and 3-sums.)10.6 Surface Embeddings of GraphsDuring the nineteenth century, in their attempts to discover generalizations ofEuler's Formula (10.2) and the Four-Colour Conjecture (discussed in the nextchapter),graph theorists were led to the study of embeddings of graphs on surfaces10.6 Surface Embeddings of Graphs 275 k vertices. The graph obtained from their union G1 ∪ G2 by deleting the edges of G1 ∩ G2 is called the k-sum of G1 and G2. a) Show that if G1 and G2 are planar and k = 0, 1, or 2, then the k-sum of G1 and G2 is also planar. b) Express the nonplanar graph K3,3 as a 3-sum of two planar graphs. 10.5.11 Series-Parallel Graph A series extension of a graph is the subdivision of a link of the graph; a parallel extension is the addition of a new link joining two adjacent vertices. A series￾parallel graph is one that can be obtained from K2 by a sequence of series and parallel extensions. a) Show that a series-parallel graph has no K4-minor. b) By applying Exercise 10.1.5, deduce that a graph has no K4-minor if and only if it can be obtained from K1, the loop graph L1 (a loop incident with a single vertex), and the family of series-parallel graphs, by means of 0-sums, 1-sums, and 2-sums. (G.A. Dirac) 10.5.12 Show that a graph is outerplanar if and only if it has neither a K4-minor nor a K2,3-minor. 10.5.13 Excluded K3,3-Minor Show that: a) every 3-connected nonplanar graph on six or more vertices has a K3,3-minor, b) any graph with no K3,3-minor can be obtained from the family of planar graphs and K5 by means of 0-sums, 1-sums, and 2-sums. (D.W. Hall; K. Wagner) 10.5.14 Excluded K5-Minor Show that: a) the Wagner graph, depicted in Figure 10.23, has no K5-minor, b) if G1 and G2 are two graphs, each of which is either a planar graph or the Wagner graph, then no 0-sum, 1-sum, 2-sum, or 3-sum of G1 and G2 has a K5-minor. (Wagner (1936) showed that every 4-connected nonplanar graph has a K5-minor and deduced the converse of (b), namely that any graph with no K5-minor can be obtained from the family of planar graphs and the Wagner graph by means of 0-sums, 1-sums, 2-sums, and 3-sums.) 10.6 Surface Embeddings of Graphs During the nineteenth century, in their attempts to discover generalizations of Euler’s Formula (10.2) and the Four-Colour Conjecture (discussed in the next chapter), graph theorists were led to the study of embeddings of graphs on surfaces