2018 - 2018 exam paper PDF

Preview

Summary

2018 exam paper...

Description

MA41007

University of Dundee School of Science and Engineering Examinations December 2018 BSc, MA, MSci & MMath Degrees in Mathematics MA41007 Graph Theory Time allowed: TWO hours

Instructions There are SEVEN questions. Candidates must answer ALL questions. The value of each part of a question is given in square brackets. Approved calculators may be used in this examination.

Do not turn over this question paper until instructed to by the Senior Invigilator MA41007

Page 1 of 4

1. Use the reduction algorithm to show that d = (5, 5, 5, 5, 5, 5, 4, 3, 3) is graphic, give an example of a simple graph with this degree sequence and show that all simple graphs with this degree sequence are connected.

[12 Marks]

2. Define the edge-connectivity, λ , and the connectivity, κ, for a connected graph G and prove that κ ≤ λ ≤ δ, where δ is the minimum degree of the vertices in G.

[10 Marks]

3. (a) For each of the following, either give an example or, if no such graph exists, explain why. (i) An Eulerian tree, (ii) A Semi-Hamiltonian tree, (iii) A Hamiltonian bi-partite graph.

[7 Marks]

(b) Construct an Euler trail for this graph.

[5 Marks]

4. (a) Prove by induction on n that a tree of order n has (n − 1) edges.

[10 Marks]

(b) Prove that if a tree of order n has maximum vertex degree ∆, then n ≥ ∆ + 1. [6 Marks]

MA41007

Page 2 of 4

5. (a) Give the definition of a spanning tree of a connected graph G.

[3 Marks]

(b) How many labeled spanning trees does the following graph have?

[8 Marks] (c) Obtain a minimum weight spanning tree for the graph shown

[5 Marks]

6. Determine whether or not the graph G below is planar, giving appropriate reasoning for your answer.

Embed G on the torus.

MA41007

[8 Marks]

Page 3 of 4

7. (a) Euler’s formula states that for a graph G of order n, size m, genus g and with f faces, n − m + f = 2 − 2g. (i) Prove that if G is a toroidal graph with size m and order n, then [8 Marks]

m ≤ 3n. (ii) Prove that KN is toroidal

⇒

N ≤ 7.

[6 Marks]

(b) Use the result from part (a) (i) to prove that for any toroidal graph, δ ≤ 6.

[4 Marks]

(c) Given that K7 is toroidal, explain why 6 colours are not enough to colour all toroidal graphs.

[2 Marks]

(d) Use the result from part (b) to prove by induction on the order n, that 7 colours are sufficient to colour any toroidal graph.

[6 Marks]

END OF PAPER

MA41007

Page 4 of 4...