MT412C - Graph Theory 2020
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
January 2020
MT412C - Graph Theory
1. (a) Suppose that G is a tree with #V (G) = n > 1. Prove that #E(G) = n - 1.
(b) Let
Are G and H isomorphic? Justify your answer.
(c) Use the Erd¨os-Gallai Theorem to determine if (3, 3, 2, 1, 1) is a graphic se- quence.
2. (a) Let n > 2. Assume that
i. di e N, 1 < i < n, and
ii.
Prove that (d_ , dl , . . . . . . , dn ) is the degree sequence of a tree. (b) Use the Havel-Hakimi algorithm to show that
(5, 5, 4, 4, 4, 3, 3, 2)
is a graphic sequence and to construct a graph which has this degree sequence. Indicate each step on your graph.
3. (a) Prove that Qn is Hamiltonian for n > 2.
(b) Determine which of the the following graphs is bipartite:
If a graph is bipartite then redraw the graph in bipartite form. If not, supply a reason to justify your answer.
4. (a) Let
Find its chromatic polynomial PG (k). Simplify your answer. Hence or other-wise find its chromatic number χ(G).
(b) State and prove Euler’s formula for planar graphs.
2021-12-30