1. Consider the following labelled graph
(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
|
(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).