| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Simple and connected definitions |
| Difficulty | Easy -1.8 This question tests only basic definitions (simple graph, connected graph) with minimal problem-solving. Parts (i-ii) require recalling definitions, part (iii) is straightforward application, and part (iv) involves simple counting of complement edges within disconnected components—all routine for D1 level with no novel insight required. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected |
| Answer | Marks | Guidance |
|---|---|---|
| (i) No repeated arcs. No loops | B1 | B1 |
| (ii) Two disconnected sets, {A,B,D,F} and {C,E,G,H} | M1 A1 | |
| (iii) [Graph showing network with 6 arcs added] | M1 A1 | |
| (iv) \(4 \times 4 = 16\) or \(\binom{8}{2} - 12 = 28 - 12 = 16\) | B1 |
**(i)** No repeated arcs. No loops | B1 | B1
**(ii)** Two disconnected sets, {A,B,D,F} and {C,E,G,H} | M1 A1 |
**(iii)** [Graph showing network with 6 arcs added] | M1 A1 |
**(iv)** $4 \times 4 = 16$ or $\binom{8}{2} - 12 = 28 - 12 = 16$ | B1 |3 Consider the following graph in which the arcs are straight lines.\\
\includegraphics[max width=\textwidth, alt={}, center]{71ca9c4e-573b-43b7-910d-4bd610af6b27-3_928_938_317_566}\\
(i) Explain how you know that the graph is simple.\\
(ii) Explain how you know that the graph is not connected.\\
(iii) On the copy of the graph in your answer book, add as many arcs as you can whilst keeping it both simple and not connected. Give the number of arcs which you have added.\\
(iv) Imagine that a new graph is produced in which two vertices are connected if there is no connection between them, direct or indirect, on the original graph. How many arcs would this new graph have?
\hfill \mbox{\textit{OCR MEI D1 2010 Q3 [8]}}