Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MA2815
Graph Theory
1. a. Find the number of spanning trees in the following graph: [8 marks]
b. Add an edge between the vertices of the graph above such that the number of spanning trees
(i) increases,
(ii) decreases,
(iii) does not change,
or explain why it is impossible. Justify your answer. [6 marks]
2. Show that the following sequence
6 6 6 5 5 5 4 4 4 3 3 3
is the degree sequence of a graph, and construct a graph with such a degree sequence. [6 marks]
3. a. Let G be a graph such that neither G nor its complement G has a cycle. Show that G can have at most 4 vertices. [6 marks]
b. Let G be a regular graph with 2m, m ≥ 2, vertices. Show that either G or its complement G is Hamiltonian. [6 marks]
c. Give an example of a Hamiltonian graph that does not satisfy the as-sumptions of Ore’s theorem. [3 marks]
d. Let G be a 3?regular disconnected graph with 2m vertices. Show that its complement G is Eulerian. [5 marks]
e. Show that there is no 4?regular bipartite planar graph. [5 marks]
4. Find the chromatic number of the following graph. Explain your reasoning. [5 marks]