27410 Planar GraphsG1G2Fig. 10.22. Apply Algorithm 10.36 to these graphs (Exercise 10.5.4)(Bienstock and Dean (1993) have shown that cr(G) = cr(G) if G is simpleand cr(G) ≤ 3. They have also given examples of graphs G with cr(G) = 4 <cT(G).)b) Show that c(Km.n) ≤ [m/2][(m -1)/2][n/2]L(n - 1)/2],(It was conjectured by P. Turan that this bound is best possible.)10.5.7 Using Kuratowski's Theorem (10.30), show that a graph is planar if andonly if the bridge-overlap graph of each cycle is bipartite.(W.T.TUTTE)10.5.8 A basis of the cycle space of a graph is a 2-basis if each member of thebasis is a cycle of the graph, and each edge of the graph lies in at most two ofthese cyclesa) Show that:i) the cycle space of any planar graph has a 2-basis.ii)thecvclespaces ofKandKa3donothave2-basesb) A theorem due to MacLane (1937) states that a graph is planar if and only ifits cycle spacehas a 2-basis.Deduce MacLane's Theorem from Kuratowski'sTheorem (10.30)10.5.9 A graph H is called an algebraic dual of a graph G if there is a bijectionΦ : E(G) - E(H) such that a subset C of E(G) is a cycle of G if and only if (C)is a bond of Ha) Show thati) every planar graph has an algebraic dual.i) Ks and K3.3 do not have algebraic dualsb) A theorem due to Whitney (1932c) states that a graph is planar if and onlyif it has an algebraic dual. Deduce Whitney's Theorem from Kuratowski'sTheorem (10.30).10.5.10 k-SUMLet Gi and G, be two graphs whose intersection Gi nG2 is a complete graph on274 10 Planar Graphs 1 1 2 2 3 3 5 4 5 4 6 6 7 7 8 8 G1 G2 Fig. 10.22. Apply Algorithm 10.36 to these graphs (Exercise 10.5.4) (Bienstock and Dean (1993) have shown that cr(G) = cr(G) if G is simple and cr(G) ≤ 3. They have also given examples of graphs G with cr(G)=4 < cr(G).) b) Show that cr(Km,n) ≤ m/2(m − 1)/2n/2(n − 1)/2. (It was conjectured by P. Tur´an that this bound is best possible.) 10.5.7 Using Kuratowski’s Theorem (10.30), show that a graph is planar if and only if the bridge-overlap graph of each cycle is bipartite. (W.T. Tutte) 10.5.8 A basis of the cycle space of a graph is a 2-basis if each member of the basis is a cycle of the graph, and each edge of the graph lies in at most two of these cycles. a) Show that: i) the cycle space of any planar graph has a 2-basis, ii) the cycle spaces of K5 and K3,3 do not have 2-bases. b) A theorem due to MacLane (1937) states that a graph is planar if and only if its cycle space has a 2-basis. Deduce MacLane’s Theorem from Kuratowski’s Theorem (10.30). 10.5.9 A graph H is called an algebraic dual of a graph G if there is a bijection φ : E(G) → E(H) such that a subset C of E(G) is a cycle of G if and only if φ(C) is a bond of H. a) Show that: i) every planar graph has an algebraic dual, ii) K5 and K3,3 do not have algebraic duals. b) A theorem due to Whitney (1932c) states that a graph is planar if and only if it has an algebraic dual. Deduce Whitney’s Theorem from Kuratowski’s Theorem (10.30). 10.5.10 k-Sum Let G1 and G2 be two graphs whose intersection G1 ∩ G2 is a complete graph on