| Exam Board | AQA |
|---|---|
| Module | Further AS Paper 2 Discrete (Further AS Paper 2 Discrete) |
| Year | 2019 |
| Session | June |
| Marks | 6 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Matchings and Allocation |
| Type | Bipartite graph definition or properties |
| Difficulty | Easy -1.2 This question tests basic definitions and straightforward application of bipartite graph concepts. Part (a) is pure recall, part (b)(i) is a routine construction from given information, part (b)(ii) requires simple observation of the graph, and part (b)(iii) involves systematic enumeration of matchings—all standard textbook exercises with no novel problem-solving required. |
| Spec | 7.02e Bipartite graphs: K_{m,n} notation8.03a Binary operations: and their properties on given sets8.03b Cayley tables: construct for finite sets under binary operation8.03c Group definition: recall and use, show structure is/isn't a group |
| Answer | Marks | Guidance |
|---|---|---|
| A bipartite graph is one in which the vertices can be split into two sets where no edge connects vertices in the same set | B1 | Must reference two sets of vertices AND that vertices of the same set are not connected |
| Answer | Marks |
|---|---|
| Sets up 10 correctly labelled vertices (abbreviations acceptable) | M1 |
| Draws correct bipartite graph showing all connections (Jay, Kay, Lee, Mel, Nish connected to Bassoon, Clarinet, Flute, Oboe, Violin) | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| The vertex for Nish is not connected to the vertex for bassoon | E1 | Must use graph theory terminology; alternatively may state Nish is only connected to flute, oboe and violin |
| Answer | Marks | Guidance |
|---|---|---|
| Draws at least one correct subgraph | M1 | |
| Draws both correct subgraphs and no others | A1 | Two separate bipartite graphs shown |
# Question 4:
## Part 4(a):
| A bipartite graph is one in which the vertices can be split into two sets where no edge connects vertices in the same set | B1 | Must reference two sets of vertices AND that vertices of the same set are not connected |
## Part 4(b)(i):
| Sets up 10 correctly labelled vertices (abbreviations acceptable) | M1 | |
| Draws correct bipartite graph showing all connections (Jay, Kay, Lee, Mel, Nish connected to Bassoon, Clarinet, Flute, Oboe, Violin) | A1 | |
## Part 4(b)(ii):
| The vertex for Nish is not connected to the vertex for bassoon | E1 | Must use graph theory terminology; alternatively may state Nish is only connected to flute, oboe and violin |
## Part 4(b)(iii):
| Draws at least one correct subgraph | M1 | |
| Draws both correct subgraphs and no others | A1 | Two separate bipartite graphs shown |
---4
\begin{enumerate}[label=(\alph*)]
\item State the definition of a bipartite graph.
4
\item A jazz quintet has five musical instruments: bassoon, clarinet, flute, oboe and violin. Jay, Kay, Lee, Mel and Nish are musicians and each plays a musical instrument in the jazz quintet.
Jay knows how to play the bassoon and the clarinet.\\
Kay knows how to play the bassoon, the oboe and the violin.\\
Lee knows how to play the clarinet and the flute.\\
Mel knows how to play the clarinet, the oboe and the violin.\\
Nish knows how to play the flute, the oboe and the violin.
4 (b) (i) Draw a graph to show which musicians know how to play which instruments.
4 (b) (ii) Nish arrives late to a jazz quintet rehearsal.
Each of the other four musicians is already playing an instrument:
\begin{displayquote}
Jay is playing the clarinet\\
Kay is playing the oboe\\
Lee is playing the flute\\
Mel is playing the violin.
\end{displayquote}
Explain how the graph in part (b)(i) shows that there is no instrument available that Nish knows how to play.
4 (b) (iii) When Nish arrives the rehearsal stops. When they restart the rehearsal, Nish is playing the flute.
Draw all possible subgraphs of the graph in part (b)(i) that show how Jay, Kay, Lee and Mel can each be assigned a unique musical instrument they know how to play.\\[0pt]
[2 marks]
\end{enumerate}
\hfill \mbox{\textit{AQA Further AS Paper 2 Discrete 2019 Q4 [6]}}