| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Moderate -0.8 This is a straightforward D1 question testing basic graph theory definitions and standard results. Parts (i)-(ii) require recall that minimum arcs = n-1 (tree) and maximum = n(n-1)/2 (complete graph). Part (iii) applies the Eulerian condition (even degrees) to limit arcs. Part (iv) is routine identification of odd-degree vertices. All parts are textbook exercises with no problem-solving or novel insight required, making this easier than average A-level maths. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02c Graph terminology: walk, trail, path, cycle, route7.02g Eulerian graphs: vertex degrees and traversability |
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 What is the minimum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
\item What is the maximum number of arcs that a simply connected graph with six vertices can have? Draw an example of such a graph. [2]
\item What is the maximum number of arcs that a simply connected Eulerian graph with six vertices can have? Explain your reasoning. [2]
\item State how you know that the graph below is semi-Eulerian and write down a semi-Eulerian trail for the graph. [2]
\end{enumerate}
\includegraphics{figure_2}
\hfill \mbox{\textit{OCR D1 2012 Q2 [8]}}