This question was a very important exercise in turning proofs into
- There were lots of brute force search algorithms. This usually
result in an algorithm which took a long time to run in the worst
case (around n factorial) or the algorithm could get stuck (or did
not always find a Hamiltonian path).
- Some algorithms returned "no Hamiltonian cycle" in some cases. By
Dirac's theorem, this case should never occur.
- Some people provided a sample run of their algorithm rather than
a proof. A proof certifies correctness for all cases whereas a
sample run only guarantee correctness for a single case.
- An example is not a proof of correctness for any method.
- For part b), depending on the method used, it may be necessary to
check separate cases for odd and even values of
- Some people assumed that |V(T1)|=|V(T2)|
which was not given as an assumption.
- Some people proved that there exists and edge whose removal
disconnects the tree (rather for all edges).
Question 4 and 5
These were mostly OK.
This is the question where a proof using "upwards induction" would
miss many important cases (and the main idea of the proof).
- A lot of students used "upward induction" for part b). [UI] was
marked on those copies. Please refer to the notes on common errors in
- Some students have a long and clear
explanations for their construction but badly explained
the core reasoning of their argument.
The answers to this question were generally good.
- A lot of people didn't clearly explain the steps of the
algorithms for a) and b).
- For c), some tried to argue that G is bipartite the property |S| &le
|N(S)|. Of course, G is not necessarily bipartite (e.g.,
K4). This was one of the more difficult questions where
a counter-example exists. The question was meant for connected
graphs only. But disconnected graphs were accepted as a solution.
Some people didn't get the question because they didn't define a
Most people got their answer from Wikipedia. Please cite your source
in this case (many did not). Also, make sure you give all definitions
not seen in class (if you use it).
- A lot of students, again, used "upward induction" for a) and b). [UI] was
marked on those copies. Please refer to the notes on common errors
- Some students copied a proof from the internet which involved
colouring edges and other concepts not seen in class. The source
should be provided in that case and all new definitions should be
given. Even with a theorem and proof obtained online, some students
incorrectly applied the copied theorem.
Question 3 and Question 4
- Some students didn't show that they could generate all decks/matchings,
[CGA] was written on those copies.
- Some students didn't check that they weren't generating copies of
the same deck/matching, [CC] was written on those copies.
- For question 4b), a lot of people did a case analysis which
involved the "best" that could happen (without proving why is was
"best"). 4b) was a rather tricky question involving the pigeonhole