Starting with a $25 \mathrm{~cm}$ by $4 \mathrm{~cm}$ rectangular strip of paper, make a model of a Möbius strip in the usual way by twisting the strip of paper through 180 degrees and then gluing/taping the two short edges together. Label the vertices of the rectangle $A, B, A^{\prime}, B^{\prime}$ so that the short edges are $A B$ and $A^{\prime} B^{\prime}$, the long edges are $A B^{\prime}$ and $B A^{\prime}$, and such that when the two short edges are glued we have $A$ glued to $A^{\prime}$ and $B$ glued to $B^{\prime}$.

Then cut the model as follows. Starting at a point which is $1 \mathrm{~cm}$ from the boundary of the Möbius strip, cut parallel to the boundary (so the cut is a constant distance of $1 \mathrm{~cm}$ from the boundary at all times) until the cut returns to its starting point.
(a) ( 2 marks) Describe briefly what happens in non-technical and non-mathematical language. Include mention of the measurements of the resulting pieces of paper.
(b) (2 marks) Before the cut is made, the model represents a Möbius strip. What surfaces are represented by the model after the cut has been made.
(c) (5 marks) Fully explain your answer to Part (b). Your answer should include an appropriately labeled diagram (or diagrams), it should explain why the resulting surfaces are what you say they are, and it should include a description of which pieces of the original rectangle make up the resulting surfaces.

( 10 marks) The number of pairwise non-isomorphic 3-regular graphs of order 8 is 6, the number of pairwise non-isomorphic 3-regular graphs of order 10 is 21 , and the number of pairwise non-isomorphic 3-regular graphs of order 14 is 540 . Using this information, determine the number of pairwise non-isomorphic connected 3-regular graphs of order 14 . By “number of pairwise non-isomorphic 3-regular graphs of order $n$ ” we mean the number of elements in a set $X$ such that every element of $X$ is a 3-regular graph of order $n$, any two distinct elements of $X$ are not isomorphic, and for any 3 -regular graph $G$ of order $n$ there is an element of $X$ that is isomorphic to $G$.

( 6 marks) Let $G$ be a regular graph. Prove that every bridge of $G$ is in every perfect matching of $G$

Let $n \geq 2$ be a positive integer.
(a) (8 marks) Prove that there is a tree with degree sequence $d_{1}, d_{2}, \ldots, d_{n}$ if and only if $d_{i} \geq 1$ for each $i \in{1,2, \ldots, n}$, and $d_{1}+d_{2}+\cdots+d_{n}=2 n-2$
(b) ( 7 marks) Let $t(n)$ denote the number of pairwise non-isomorphic trees of order $n$, and let $s(n)$ denote the number of partitions of $2 n-2$ into parts where the largest part has size $n$. Prove that $t(n)>s(n)$ if and only if $n \geq 6$