Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

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.

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.