MT412C - Graph Theory 2021
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
January 2021
MT412C - Graph Theory
1. (a) Let
Determine if G and H are isomorphic. If G and H are isomorphic supply an isomorphism φ : V (G) −→ V (H). If not, justify your answer. [10 Marks]
(b) Draw two non-isomorphic graphs which have degree sequence (2, 2, 2, 2, 2, 2, 2). Justify your answer. [10 Marks]
(c) Is (4, 3, 3, 1, 1, 1, 1) the degree sequence of a tree? Justify your answer. [5 Marks]
2. (a) Use the Erd˝os-Gallai Theorem to determine if (5, 5, 5, 4, 4, 3, 2) is a graphic sequence. [10 Marks]
(b) Use the Havel-Hakimi algorithm to determine if (8, 7, 5, 4, 4, 3, 2, 1, 1) is a graphic sequence. [10 Marks]
(c) A graph G has degree sequence (3, 2, 2, 2, 1, 1, 1). Is G isomorphic to the complete graph K7 ? [5 Marks]
3. (a) Explain why the hypercube graph, Qn , is bipartite and write down the partite sets for Q2 and Q3 . [15 Marks]
(b) Suppose that G is a 2-colourable graph with vertices coloured red and blue. Suppose that G has a Hamilton Cycle. Prove that there are the same number of red and blue vertices. [10 Marks]
4. (a) Let G be the graph
Find its chromatic polynomial PG (k). Hence or otherwise find G’s chromatic number. [15 Marks]
(b) Let K3,3 have partite sets {1, 3, 5} and {2, 4, 6}. Let G = K3,3 − {1, 4}. Show, by drawing the graph, that G is planar. [10 Marks]
2021-12-30