| Exam Board | OCR |
|---|---|
| Module | FD1 AS (Further Decision 1 AS) |
| Year | 2018 |
| Session | March |
| Marks | 8 |
| Topic | Graph Theory Fundamentals |
| Type | Bipartite graph properties |
| Difficulty | Challenging +1.2 Part (i) is trivial recall of bipartite graph formula. Parts (ii)-(iii) require understanding of permutations and the pigeonhole principle with moderate multi-step reasoning. Part (iv) tests generalization. While this involves proof and combinatorial reasoning beyond routine exercises, the concepts are standard FD1 material and the steps are guided, making it moderately above average but not exceptionally challenging. |
| Spec | 5.01a Permutations and combinations: evaluate probabilities7.01c Pigeonhole principle7.01e Permutations: ordered subsets of r from n elements7.01j Selections with several constraints7.02e Bipartite graphs: K_{m,n} notation |
| Answer | Marks | Guidance |
|---|---|---|
| 5 | 8 | 3 |
Question 5:
5
5 | 8 | 35 (i) How many arcs does the complete bipartite graph $K _ { 5,5 }$ have?
A subgraph of $K _ { 5,5 }$ contains 5 arcs joining each of the elements of the set $\{ 1,2,3,4,5 \}$ to an element in a permutation of the set $\{ 1,2,3,4,5 \}$. Suppose that $r$ is connected to $p ( r )$ for $r = 1,2,3,4,5$.\\
(ii) How many permutations would have $p ( 1 ) \neq 1$ ?\\
(iii) Using the pigeonhole principle, show that for every permutation of $\{ 1,2,3,4,5 \}$, the product $\Pi _ { r = 1 } ^ { 5 } ( r - p ( r ) )$ is even (i.e. an integer multiple of 2, including 0 ).\\
(iv) Is the result in part (iii) true when the permutation is of the set $\{ 1,2,3,4,5,6 \}$ ? Give a reason for your answer.
\hfill \mbox{\textit{OCR FD1 AS 2018 Q5 [8]}}