3.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_595_1269_207_397}
\captionsetup{labelformat=empty}
\caption{Figure 3}
\end{figure}
Figure 3 shows a graph G that contains \(17 \operatorname { arcs }\) and 8 vertices.
- State how many arcs there are in a spanning tree for G .
(1) - Explain why a path on G cannot contain 10 vertices.
(2) - Determine the number of arcs that would need to be added to G to make G a complete graph with 8 vertices.
(1)
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5b18e92c-540e-4e89-8d60-d60294f50dda-04_684_1326_1420_370}
\captionsetup{labelformat=empty}
\caption{Figure 4}
\end{figure}
Figure 4 shows a weighted graph. - Use Prim's algorithm, starting at C , to find the minimum spanning tree for the weighted graph. You must clearly state the order in which you select the arcs of the tree.
(3) - State the weight of the minimum spanning tree.
(1)