| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2011 |
| Session | June |
| Marks | 9 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Impossibility proofs for degree sequences |
| Difficulty | Standard +0.3 This is a multi-part question testing fundamental graph theory concepts (handshaking lemma, tree properties, Eulerian paths) through straightforward applications. While it requires understanding of definitions and basic theorems, each part involves direct application of standard results rather than novel problem-solving. The calculations are simple (counting degrees, applying sum of degrees = 2×edges) and the explanations follow directly from textbook definitions. Slightly easier than average due to its structured, definition-based nature. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02g Eulerian graphs: vertex degrees and traversability |
| Answer | Marks | Guidance |
|---|---|---|
| (i) (Cannot have three odd vertices – total order must be even) | B1 | Note graph not be connected or connected cases |
| (ii) The vertices (i would either connect to or compare to another) The vertices one of the other vertices (once) | B1 | |
| (iii) \(5 > r \! + 1\) (but r-1 on its own not enough) Not a description of a specific case | B1 B1 | |
| (iv) A tree must have at least two nodes of order 1 Eulerian all nodes are all even order Conditions all nodes are connected | B1 | |
| A tree cannot contain a cycle Two nodes of order 1 | B1 | Need repeat 2 trees |
| (v) Would either an Eulerian or a semi- Eulerian graph = 2 odd nodes. Condition "all odd nodes" | B1 B1 | [Note must need a biased cycle] |
(i) (Cannot have three odd vertices – total order must be even) | B1 | Note graph not be connected or connected cases
(ii) The vertices (i would either connect to or compare to another) The vertices one of the other vertices (once) | B1 |
(iii) $5 > r \! + 1$ (but r-1 on its own not enough) Not a description of a specific case | B1 B1 |
(iv) A tree must have at least two nodes of order 1 Eulerian all nodes are all even order Conditions all nodes are connected | B1 |
A tree cannot contain a cycle Two nodes of order 1 | B1 | Need repeat 2 trees
(v) Would either an Eulerian or a semi- Eulerian graph = 2 odd nodes. Condition "all odd nodes" | B1 B1 | [Note must need a biased cycle]
---3 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.\\
(i) Explain why it is impossible to draw a graph with exactly five vertices of orders $1,2,3,4$ and 5.\\
(ii) Explain why there is no simply connected graph with exactly five vertices of orders $2,2,3,4$ and 5 . State which of the properties 'simple' and 'connected' cannot be achieved.\\
(iii) Calculate the number of arcs in a simply connected graph with exactly five vertices of orders 1 , 1, 2, 2 and 4 . Hence explain why such a graph cannot be a tree.\\
(iv) Draw a simply connected semi-Eulerian graph with exactly five vertices that is also a tree. By considering the orders of the vertices, explain why it is impossible to draw a simply connected Eulerian graph with exactly five vertices that is also a tree.
In the graph below the vertices represent buildings and the arcs represent pathways between those buildings.\\
\includegraphics[max width=\textwidth, alt={}, center]{cec8d4db-4a72-43a3-88f3-ff9df2a11d2c-4_426_1081_1297_532}\\
(v) By considering the orders of the vertices, explain why it is impossible to walk along these pathways in a continuous route that uses every arc once and only once. Write down the minimum number of arcs that would need to be travelled twice to walk in a continuous route that uses every arc at least once.
\hfill \mbox{\textit{OCR D1 2011 Q3 [9]}}