5 A garden centre sells tulip bulbs in mixed packs. The cost of each pack and the number of tulips of each colour are given in the table.

\begin{center}
\begin{tabular}{ l | c | c | c | c | c }
 & Cost $( \pounds )$ & Red & White & Yellow & Pink \\
\hline
Pack A & 50 & 25 & 25 & 25 & 25 \\
\hline
Pack B & 48 & 40 & 30 & 30 & 0 \\
\hline
Pack C & 53 & 20 & 30 & 40 & 10 \\
\hline
\end{tabular}
\end{center}

Dirk is designing a floral display in which he will need the number of red tulips to be at most 50 more than the number of white tulips, and the number of white tulips to be less than or equal to twice the number of pink tulips. He has a budget of $\pounds 240$ and wants to find out which packs to buy to maximise the total number of bulbs.

Dirk uses the variables $x , y$ and $z$ to represent, respectively, how many of pack A , pack B and pack C he buys. He sets up his problem as an initial simplex tableau, which is shown below.

Initial tableau\\
Row 1\\
Row 2\\
Row 3\\
Row 4

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & RHS \\
\hline
1 & - 1 & - 1 & - 1 & 0 & 0 & 0 & 0 \\
\hline
0 & 0 & 1 & - 1 & 1 & 0 & 0 & 5 \\
\hline
0 & - 5 & 6 & 2 & 0 & 1 & 0 & 0 \\
\hline
0 & 50 & 48 & 53 & 0 & 0 & 1 & 240 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\roman*)]
\item Show how the constraint on the number of red tulips leads to one of the rows of the tableau.

The tableau that results after the first iteration is shown below.\\
After first iteration\\
Row 5\\
Row 6\\
Row 7\\
Row 8

\begin{center}
\begin{tabular}{ | c | c | c | c | c | c | c | c | }
\hline
$P$ & $x$ & $y$ & $z$ & $s$ & $t$ & $u$ & RHS \\
\hline
1 & 0 & - 0.04 & 0.06 & 0 & 0 & 0.02 & 4.8 \\
\hline
0 & 0 & 1 & - 1 & 1 & 0 & 0 & 5 \\
\hline
0 & 0 & 10.8 & 7.3 & 0 & 1 & 0.1 & 24 \\
\hline
0 & 1 & 0.96 & 1.06 & 0 & 0 & 0.02 & 4.8 \\
\hline
\end{tabular}
\end{center}
\item Which cell was used as the pivot?
\item Explain why row 2 and row 6 are the same.
\item (a) Read off the values of $x , y$ and $z$ after the first iteration.\\
(b) Interpret this solution in terms of the original problem.
\item Identify the variable that has become non-basic. Use the pivot row of the initial tableau to eliminate $x$ algebraically from the equation represented by Row 1 of the initial tableau.

The feasible region can be represented graphically in three dimensions, with the variables $x , y$ and $z$ corresponding to the $x$-axis, $y$-axis and $z$-axis respectively. The boundaries of the feasible region are planes. Pairs of these planes intersect in lines and at the vertices of the feasible region these lines intersect.
\item The planes defined by each of the new basic variables being set equal to 0 intersect at a point. Show how the equations from part (v) are used to find the values $P$ and $x$ at this point.

A planar graph $G$ is described by the adjacency matrix below.

$\quad$\\
$A$\\
$B$\\
$C$\\
$D$\\
$E$\\
$F$ $\left( \begin{array} { c c c c c c } A & B & C & D & E & F \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 \end{array} \right)$
\item Draw the graph $G$.
\item Use Euler's formula to verify that there are four regions. Identify each region by listing the vertices that define it.
\item Explain why graph $G$ cannot have a Hamiltonian cycle that includes the edge $A B$. Deduce how many Hamiltonian cycles graph $G$ has.

A colouring algorithm is given below.

STEP 1: Choose a vertex, colour this vertex using colour 1.

STEP 2: If all vertices are coloured, STOP. Otherwise use colour 2 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 1 .

STEP 3: If all vertices are coloured, STOP. Otherwise use colour 1 to colour all uncoloured vertices for which there is an edge that joins that vertex to a vertex of colour 2 .

STEP 4: Go back to STEP 2.
\item Apply this algorithm to graph $G$, starting at $E$. Explain how the colouring shows you that graph $G$ is not bipartite.

By removing just one edge from graph $G$ it is possible to make a bipartite graph.
\item Identify which edge needs to be removed and write down the two sets of vertices that form the bipartite graph.

Graph $G$ is augmented by the addition of a vertex $X$ joined to each of $A , B , C , D , E$ and $F$.
\item Apply Kuratowski's theorem to a contraction of the augmented graph to explain how you know that the augmented graph has thickness 2.
\end{enumerate}

\hfill \mbox{\textit{OCR Further Discrete  Q5 [13]}}