代做MA2815 Graph Theory 2020调试数据库编程

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]