MAST20018 – Discrete Mathematics and Operations Research Assignment 4 Place in your tutor's box by 5pm Friday 21st October 2016 1. Consider the following labelled graph: d a b c e f g h i j (a) State an upper-bound and a lower-bound on the vertex-chromatic number of the graph, and give reasons for your answers. (b) Find an optimal colouring of the graph. (c) To which of the following classes does the graph belong: chordal graphs, trees, bipartite graphs, perfect graphs? Provide reasons for your answers. (d) Beginning with the matching M = {(e, f)}, extend M into a maximum matching by repeatedly finding augmenting paths. At each step you should increase the number of edges in the matching by one. Explicitly show each step of the process. Recall: an augmenting path is an alternating path that joins two "exposed" vertices. An edge between two exposed nodes is also regarded as an augmenting path. (e) State a lower-bound on the edge-chromatic number of the graph, and give a reason for your answer. 2. Suppose teachers x1, x2, x3, x4 have to teach classes y1, y2, y3, y4, y5, y6 according to the following teacher/class allocation table: y1 y2 y3 y4 y5 y6 x1 0 0 1 0 1 1 x2 1 0 1 0 0 2 x3 1 1 1 0 0 1 x4 2 0 0 1 1 0 1MAST20018 – Discrete Mathematics and Operations Research (a) What is the minimum possible number of periods used in this allocation. How do we know this without doing a decomposition? (b) Calculate the minimum number of periods using a single 1's decomposition. (c) Construct a timetable using the minimum number of periods. 3. For n ! 3, find the number of distinct perfect matchings in the cycle Cn of length n. Justify your answer. 4. Suppose that T is a tree (a connected graph without cycles) with n vertices and that every vertex of T has degree 1 or 3. (a) Prove rigorously that n is even. (b) Prove rigorously that T has exactly (n + 2)/2 leaves (vertices of degree 1). 2