| Exam Board | OCR |
|---|---|
| Module | Further Discrete AS (Further Discrete AS) |
| Session | Specimen |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Graph Theory Fundamentals |
| Type | Tree properties |
| Difficulty | Standard +0.8 This is a Further Maths question requiring systematic enumeration of tree structures and understanding of graph-theoretic properties. While the concepts are accessible, it demands careful reasoning about vertex orders, isomorphism classes, and the relationship between tree structure and degree sequences—going beyond routine application to require mathematical insight and systematic case analysis. |
| Spec | 7.02b Graph terminology: tree, simple, connected, simply connected7.02j Isomorphism: of graphs, degree sequences |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (i) | B1 |
| [1] | 1.1 | These three graphs and no others |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (ii) | e.g. Six vertices so need 6 positive integers |
| Answer | Marks |
|---|---|
| two vertex orders have value 1 | B3 |
| [3] | 1.1 |
| Answer | Marks |
|---|---|
| 2.5 | n |
| Answer | Marks |
|---|---|
| property | Award B2 for three properties if |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (iii) | (cid:94)1,1,1,1,1,5(cid:96) (cid:94)1,1,1,1, 2, 4(cid:96) |
| Answer | Marks |
|---|---|
| (cid:94)1,1, 2, 2, 2, 2(cid:96) | M1 |
| Answer | Marks |
|---|---|
| [2] | i1.1 |
| Answer | Marks |
|---|---|
| 1.1 | m |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | (iv) | p |
| S | e |
| Answer | Marks |
|---|---|
| [2] | 1.1 |
| 1.1 | At least four correct graphs |
| Answer | Marks |
|---|---|
| (cid:94)1,1,1, 2, 2,3(cid:96) are shown | Other possibility for |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | 7 | - |
| Answer | Marks |
|---|---|
| 5(iv) | n |
Question 5:
5 | (i) | B1
[1] | 1.1 | These three graphs and no others | May appear in any equivalent
variation
5 | (ii) | e.g. Six vertices so need 6 positive integers
e.g. 5 arcs so sum of vertex orders (cid:32)10
e.g. Tree must have at least two ‘ends’ so at least
two vertex orders have value 1 | B3
[3] | 1.1
1.1
2.5 | n
Be1 for each independently correct
property | Award B2 for three properties if
incorrect or inconsistent
terminology used
5 | (iii) | (cid:94)1,1,1,1,1,5(cid:96) (cid:94)1,1,1,1, 2, 4(cid:96)
(cid:94)1,1,1,1,3,3(cid:96) (cid:94)1,1,1, 2, 2,3(cid:96)
(cid:94)1,1, 2, 2, 2, 2(cid:96) | M1
A1
[2] | i1.1
c
1.1 | m
At least four correct sets
All five correct with no extras
5 | (iv) | p
S | e
M1
A1
[2] | 1.1
1.1 | At least four correct graphs
Five correct graphs and no extras,
unless it is because both versions of
(cid:94)1,1,1, 2, 2,3(cid:96) are shown | Other possibility for
(cid:94)1,1,1, 2, 2,3(cid:96)
5 | 7 | - | 6 | 8
--- 5(i) ---
5(i)
--- 5(ii) ---
5(ii)
n
e
m
i
c
e
p
S
--- 5(iii) ---
5(iii)
--- 5(iv) ---
5(iv) | n
e
m
i
c
e
p
S5 There are three non-isomorphic trees on five vertices.\\
(i) Draw an example of each of these trees.\\
(ii) State three properties that must be satisfied by the vertex orders of a tree on six vertices.\\
(iii) List the five different sets of possible vertex orders for trees on six vertices.\\
(iv) Draw an example of each type listed in part (iii).
\hfill \mbox{\textit{OCR Further Discrete AS Q5 [8]}}