Problem

Figure 5 shows a weighted graph that contains 12 arcs and 8 vertices.

It is given that

• no two arcs have the same weight
• $x$ and $y$ are positive integers
• arc CD is not in the minimum spanning tree for the graph

(a) Explain why $y < x + 7$

It is also given that when Prim’s algorithm, starting at A, is applied to the weighted graph, AB is the first arc selected.

(b) Show that $y > 2x$ and write down and simplify two further constraints on the values of $x$ and $y$.

(c) Represent these four constraints on Diagram 1 in the answer book.

(d) Using Diagram 1 only, write down the possible pairs of values that $x$ and $y$ can take in the form $(x, y)$.

The minimum spanning tree for the weighted graph in Figure 5 has total weight 73.

Six of the seven arcs in the minimum spanning tree are AB, AD, BC, CE, EF and GH.

(e) Determine the value of $x$ and the value of $y$. You must make your method and working clear.