1.    (a)  Draw five different trees, each with maximum degree 3 and at least five vertices.  In each example, state the number of vertices of degree 1 and the number of vertices of degree 3.

[3 marks]

(b)  Let T be an arbitrary tree with maximum degree 3. What is the relationship between the

number of vertices of degree 1 and the number of vertices of degree 3 in T?  Prove your answer using the handshaking lemma.

[7 marks]

(c)  Generalise the result for an arbitrary tree, by proving a formula for the number of vertices of degree 1 in terms of the number of vertices of degree d (for d = 3, 4, 5, . . . ).

[7 marks]

(d) A saturated hydrocarbon (also called alkane or paraffin) is a molecule formed from carbon and hydrogen atoms by adding bonds between atoms such that each carbon atom is in four bonds, each hydrogen atom is in one bond, and no sequence of bonds forms a cycle of atoms. What is the relationhip between c and h?

[3 marks]

 2. Apply the Prim-Jarn´ık algorithm presented in lectures to determine a minimum spanning tree rooted at vertex a in the following weighted graph.  Describe all steps of the algorithm.  Draw the current tree at each step of the algorithm. What is the weight of a minimum spanning tree?

[20 marks]

f

4                        5                       4

a           6           c           9           e

3.    (a)  Prove that for k > 2, for every tree T with k vertices, every graph G with

minimum degree at least k - 1 contains a subgraph isomorphic to T.

[15 marks]

(b)  Show that “k - 1” in part (a) is best possible (for every k > 2).

[5 marks]

4.  Let P3  be the path on three vertices.  Complete and prove the following simplest possible answer):

(a) A graph does not contain P3  as a subgraph if and only if

.

(b) A graph does not contain P3  as an induced subgraph if and only if

.

statements (with the

[10 marks]

[10 marks]