Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
Mathematics
MA2815
Graph Theory
2020
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]
