2 A simple graph is one in which any two vertices are directly connected by at most one arc and no vertex is directly connected to itself. A connected graph is one in which every vertex is joined, directly or indirectly, to every other vertex. A simply connected graph is one that is both simple and connected.
\begin{enumerate}[label=(\roman*)]
\item (a) Draw a simply connected Eulerian graph with exactly five vertices and five arcs.\\
(b) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which one of the vertices has order 4.\\
(c) Draw a simply connected semi-Eulerian graph with exactly five vertices and five arcs, in which none of the vertices have order 4.

A teacher is organising revision classes for her students. There will be ten revision classes scheduled into a number of sessions. Each class will run in one session only. Each student has chosen two classes to attend. The table shows which classes each student has chosen.

\begin{table}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{Revision classes}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline
Student number & C1 & C2 & C3 & C4 & M1 & M2 & S1 & S2 & D1 & D2 \\
\hline
1 & ✓ & ✓ &  &  &  &  &  &  &  &  \\
\hline
2 &  &  &  & ✓ &  &  &  &  &  & ✓ \\
\hline
3 &  &  & ✓ & ✓ &  &  &  &  &  &  \\
\hline
4 &  &  & ✓ &  &  & ✓ &  &  &  &  \\
\hline
5 &  &  &  &  &  &  &  & ✓ & ✓ &  \\
\hline
6 &  & ✓ &  &  &  & ✓ &  &  &  &  \\
\hline
7 &  &  &  &  & ✓ &  &  & ✓ &  &  \\
\hline
8 & ✓ &  &  &  &  &  & ✓ &  &  &  \\
\hline
9 &  &  &  &  &  & ✓ &  &  &  & ✓ \\
\hline
10 &  &  &  &  & ✓ &  & ✓ &  &  &  \\
\hline
\end{tabular}
\end{center}
\end{table}
\item (a) Draw a graph to show this information. Each vertex represents a class. Each arc links the two classes chosen by a student.\\
(b) Show how the teacher can arrange the classes in just two sessions, which satisfy all student choices. For example, C1 and C2 cannot be in the same session.

An extra student joins the group. This student chooses to attend the revision classes in M1 and D1.\\
(c) Explain why the teacher cannot now arrange the classes in just two sessions. Do not amend your graph from part (ii)(a).
\end{enumerate}

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