1 Two graphs A and B are shown below.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_339_585_333_386}
\captionsetup{labelformat=empty}
\caption{Graph \(A\)}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{dbf782dd-879c-4f0f-b532-246a0db9f130-2_337_579_333_1174}
\captionsetup{labelformat=empty}
\caption{Graph B}
\end{figure}
- Write down an example of a cycle on graph A .
- W hy is \(\mathrm { U } - \mathrm { Y } - \mathrm { V } - \mathrm { Z } - \mathrm { Y } - \mathrm { X }\) not a path on graph B ?
- How many arcs would there be in a spanning tree for graph A ?
- For each graph state whether it is Eulerian, semi-Eulerian or neither.
- The graphs show designs to be etched on metal plates. The etching tool is positioned at a starting point and follows a route without repeating any arcs. It may be lifted off and positioned at a new starting point. W hat is the smallest number of times that the etching tool must be positioned, including the initial position, to draw each graph?
An arc is drawn connecting Q to U , so that the two graphs become one. The resulting graph is not Eulerian.
- Extra arcs are then added to make an Eulerian graph. W hat is the smallest number of extra arcs that need to be added?