| Exam Board | OCR |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2010 |
| 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, degree sequences, Eulerian graphs). Parts (i)-(iii) require straightforward application of the handshaking lemma and basic reasoning about connectivity. Part (iv) requires systematic enumeration of degree sequences but follows standard D1 techniques. While it has many parts (8 marks total), each individual step is routine for students who know the basic theorems, making it slightly easier than average overall. |
| 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 |
|---|---|---|
| Answer | Mark | Guidance |
| Sum of orders = 2+3+4 = 9, which is odd; but sum of vertex orders must be even | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Valid graph with 4 vertices of orders 1,2,3,4 that is neither simple (loop or multiple arc) nor connected | B2 | B1 for correct orders, B1 for neither simple nor connected |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Sum of orders = 1+2+3+4 = 10 ✓ (simple possible in principle) | M1 | |
| Cannot be simple: vertex of order 3 connected to all others including vertex of order 1; but then vertex of order 1 has order ≥ 1 while the structure forces a contradiction; or cannot be connected since vertex of order 1 means one vertex has only one connection making full connectivity impossible with these orders | A1 | Accept: 'simple' cannot be achieved (multiple arc needed) or 'connected' cannot be achieved with clear reasoning |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| In an Eulerian graph all vertices must have even order; if 3 vertices have order 4, the sum contributed is 12, leaving total sum − 12 to be distributed among 2 remaining vertices; having exactly three vertices of order 4 forces an odd sum contradiction | B1 | Or: for Eulerian graph all orders even; 3 vertices order 4 uses 12 of degree sum; remaining 2 vertices orders must sum to even amount but the constraint forces a problem |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| All 5 vertices must have even order; possible order sets summing correctly: (2,2,2,2,2), (2,2,2,4,2) rearranged, (4,4,2,2,2) rearranged, (4,4,4,2,2) etc. — exactly four valid combinations | M1 | Systematic consideration of even orders |
| Four graphs drawn correctly, one example each | A1 A1 | B1 for identifying the four sets of orders, B1 each for two correctly drawn examples (up to 3 marks total) |
# Question 2:
## Part (i)
| Answer | Mark | Guidance |
|--------|------|----------|
| Sum of orders = 2+3+4 = 9, which is odd; but sum of vertex orders must be even | B1 | |
## Part (ii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Valid graph with 4 vertices of orders 1,2,3,4 that is neither simple (loop or multiple arc) nor connected | B2 | B1 for correct orders, B1 for neither simple nor connected |
## Part (iii)
| Answer | Mark | Guidance |
|--------|------|----------|
| Sum of orders = 1+2+3+4 = 10 ✓ (simple possible in principle) | M1 | |
| Cannot be simple: vertex of order 3 connected to all others including vertex of order 1; but then vertex of order 1 has order ≥ 1 while the structure forces a contradiction; or cannot be connected since vertex of order 1 means one vertex has only one connection making full connectivity impossible with these orders | A1 | Accept: 'simple' cannot be achieved (multiple arc needed) or 'connected' cannot be achieved with clear reasoning |
## Part (iv)(a)
| Answer | Mark | Guidance |
|--------|------|----------|
| In an Eulerian graph all vertices must have even order; if 3 vertices have order 4, the sum contributed is 12, leaving total sum − 12 to be distributed among 2 remaining vertices; having exactly three vertices of order 4 forces an odd sum contradiction | B1 | Or: for Eulerian graph all orders even; 3 vertices order 4 uses 12 of degree sum; remaining 2 vertices orders must sum to even amount but the constraint forces a problem |
## Part (iv)(b)
| Answer | Mark | Guidance |
|--------|------|----------|
| All 5 vertices must have even order; possible order sets summing correctly: (2,2,2,2,2), (2,2,2,4,2) rearranged, (4,4,2,2,2) rearranged, (4,4,4,2,2) etc. — exactly four valid combinations | M1 | Systematic consideration of even orders |
| Four graphs drawn correctly, one example each | A1 A1 | B1 for identifying the four sets of orders, B1 each for two correctly drawn examples (up to 3 marks total) |
---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.\\
(i) Explain why it is impossible to draw a graph with exactly three vertices in which the vertex orders are 2, 3 and 4.\\
(ii) Draw a graph with exactly four vertices of orders 1, 2, 3 and 4 that is neither simple nor connected.\\
(iii) Explain why there is no simply connected graph with exactly four vertices of orders $1,2,3$ and 4. State which of the properties 'simple' and 'connected' cannot be achieved.\\
(iv) A simply connected Eulerian graph has exactly five vertices.
\begin{enumerate}[label=(\alph*)]
\item Explain why there cannot be exactly three vertices of order 4.
\item By considering the vertex orders, explain why there are only four such graphs. Draw an example of each.
\end{enumerate}
\hfill \mbox{\textit{OCR D1 2010 Q2 [9]}}