Explain why G cannot contain a subdivision of K5, but must contain a subdivision of K3,3

Question1

(a)The connected planar graph G has degree sequence (g1, g2, g3, g4, g5, g6), And the connected planar graph H has degree sequence (2, g1, g2, g3, g4, g5, g6).

If G has f faces and m edges, find expressions for the number of faces

FH and edges mH of H in terms of f and m.

(b)The non-planar graph G has degree sequence

(2, 2, 3, 3, 3, 3, 4, 4).

(i)Explain why G cannot contain a subdivision of K5, but must contain a subdivision of K3,3

(ii) Draw two such a graphs, one in which K3,3 is a subgraph, and One in which there is a proper subdivision of K3,3 as a subgraph .

(c) Let G be the following graph.

(i)Write down a Hamiltonian cycle in G. Then, using the cycle method, prove that G is not planar.

(ii) Use a corollary of Euler`s formula to give an alternative proof that G is not planar.

(d)A school wants to schedule six sports events (badminton, cricket, football, gymnastics, swimming and tennis), but is constrained because six of the participants are involved with more than one sport, as follows.