Problem

(a) Explain why it is impossible to draw a graph with eight vertices in which the vertex orders are 1, 2, 2, 3, 3, 4, 4 and 6.

Figure 3 shows the network $T$. The numbers on the arcs represent the distances, in km, between the eight vertices, A, B, C, D, E, F, G and H.

(b) Determine whether or not A – C – D – E – C – B – F is an example of a path on $T$. You must justify your answer.

(c) Use Prim’s algorithm, starting at A, to find the minimum spanning tree for $T$. You must clearly state the order in which you select the arcs of the tree.

(d) Draw the minimum spanning tree using the vertices given in Diagram 1 in the answer book.

The weight of arc CF is now increased to a value of $x$. The minimum spanning tree for $T$ is unique and includes the same arcs as those found in (c).

(e) Write down the smallest interval that must contain $x$.