| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2013 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Game and interaction modeling |
| Difficulty | Moderate -0.5 This is a straightforward application of bipartite graph concepts requiring students to identify the graph type, calculate maximum edges using the formula for complete bipartite graphs (10×10=100), draw a simple graph from given constraints, and count edges. The calculations are arithmetic, the graph drawing is mechanical, and no proof or novel insight is required—slightly easier than average due to its routine nature. |
| Spec | 7.02a Graphs: vertices (nodes) and arcs (edges)7.02b Graph terminology: tree, simple, connected, simply connected7.02d Complete graphs: K_n and number of arcs7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| bipartite | B1 | cao |
| [1] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 100 | M1 A1 | allow for 200; cao |
| [2] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Darcy correctly matched | B1 | Darcy correct |
| Elizabeth correctly matched | B1 | Elizabeth correct |
| Panto characters correctly matched | B1 | Panto characters correct |
| [3] |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| 58 | M1 | \(18 + (8 \times 5)\) allow for 98 |
| A1 | cao | |
| [2] |
# Question 2:
## Part (i)
| Answer | Marks | Guidance |
|--------|-------|----------|
| bipartite | B1 | cao |
| **[1]** | | |
## Part (ii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 100 | M1 A1 | allow for 200; cao |
| **[2]** | | |
## Part (iii)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Darcy correctly matched | B1 | Darcy correct |
| Elizabeth correctly matched | B1 | Elizabeth correct |
| Panto characters correctly matched | B1 | Panto characters correct |
| **[3]** | | |
## Part (iv)
| Answer | Marks | Guidance |
|--------|-------|----------|
| 58 | M1 | $18 + (8 \times 5)$ allow for 98 |
| | A1 | cao |
| **[2]** | | |
---2 A small party is held in a country house. There are 10 men and 10 women, and there are 10 dances. For each dance a number of pairings, each of one man and one woman, are formed. The same pairing can appear in more than one dance. A graph is to be drawn showing who danced with whom during the evening, ignoring repetitions.\\
(i) Name the type of graph which is appropriate.\\
(ii) What is the maximum possible number of arcs in the graph?
Dashing Mr Darcy dances with every woman except Elizabeth, who will have nothing to do with him. She dances with eight different men.
Prince Charming only dances with Cinderella. Cinderella only dances with Prince Charming and with Mr Darcy.
The three ugly sisters only have one dance each.\\
(iii) Add arcs to the graph in your answer book to show this information.\\
(iv) What is the maximum possible number of arcs in the graph?
\hfill \mbox{\textit{OCR MEI D1 2013 Q2 [8]}}