2 Two simply connected graphs are shown below.
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_301}
\captionsetup{labelformat=empty}
\caption{Graph 1}
\end{figure}
\begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{10ca0bf1-beaa-4460-8f28-08f0e4e44d5c-02_307_584_1151_1178}
\captionsetup{labelformat=empty}
\caption{Graph 2}
\end{figure}
- Write down the orders of the vertices for each of these graphs.
- How many ways are there to allocate these vertex degrees to a graph with vertices \(\mathrm { P } , \mathrm { Q }\), \(\mathrm { R } , \mathrm { S } , \mathrm { T }\) and U ?
- Use the vertex degrees to deduce whether the graphs are Eulerian, semi-Eulerian or neither.
- Show that graphs 1 and 2 are not isomorphic.
- Write down a Hamiltonian cycle for graph 1.
- Use Euler's formula to determine the number of regions for graph 1.
- Identify each of these regions for graph 1 by listing the cycle that forms its boundary.