\begin{enumerate}[label=(\roman*)]
\item Explain why it is impossible to draw a graph with four vertices in which the vertex orders are 1, 2, 3 and 3. [1]
\end{enumerate}

A \textit{simple graph} is one in which any two vertices are directly joined by at most one arc and no vertex is directly joined to itself.

A \textit{connected graph} is one in which every vertex is joined, directly or indirectly, to every other vertex.

A \textit{simply connected graph} is one that is both simple and connected.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{1}
\item 
\begin{enumerate}[label=(\alph*)]
\item Draw a graph with five vertices of orders 1, 1, 2, 2 and 4 that is neither simple nor connected. [2]

\item Explain why your graph from part (a) is not semi-Eulerian. [1]

\item Draw a semi-Eulerian graph with five vertices of orders 1, 1, 2, 2 and 4. [1]
\end{enumerate}
\end{enumerate}

Six people (Ann, Bob, Caz, Del, Eric and Fran) are represented by the vertices of a graph. Each pair of vertices is joined by an arc, forming a complete graph. If an arc joins two vertices representing people who have met it is coloured blue, but if it joins two vertices representing people who have not met it is coloured red.

\begin{enumerate}[label=(\roman*)]
\setcounter{enumi}{2}
\item 
\begin{enumerate}[label=(\alph*)]
\item Explain why the vertex corresponding to Ann must be joined to at least three of the others by arcs that are the same colour. [2]

\item Now assume that Ann has met Bob, Caz and Del. Bob, Caz and Del may or may not have met one another. Explain why the graph must contain at least one triangle of arcs that are all the same colour. [2]
\end{enumerate}
\end{enumerate}

\hfill \mbox{\textit{OCR D1 2009 Q2 [9]}}