This is page is a brief commentary about what proofs are examinable. As a general rule, proofs are examinable. There are a few notable exceptions

Proofs that WILL NOT be examined

1. Ore’s theorem – you could need statement, but won’t have to prove
2. Cayley’s theorem – You need to know the statement, and how to go back and forth between a tree and its Prüfer code. But you don’t need to be able to prove these maps are inverses.
3. Various definitions of trees are equivalent
4. Kruskal’s algorithm works – you need to use the algorithm, but not prove it gives a minimal spanning tree
5. The five colour theorem. The six colour theorem won’t appear on the exam, either, but the techniques used probably will

A not necessarily complete list of proofs you might have to do:

Proofs that ARE examinable

1. Instant insanity – prove whether or not a set of cubes has a solution
2. Determine whether or not two graphs are isomorphic, with justification
3. A connected graph is Eulerian if and only if every vertex has even degree
4. Determine whether or not a graph is Hamiltonian “by hand”
5. Proving the Petersen graph is not Hamiltonian
6. Proving an Alkane is a tree
7. Proving a lower bound for the Travelling Salesman Problem
8. Proving that $K_{3,3}$ or $K_5$ not planar
9. Proving a graph isn’t planar using Kuratowski’s theorem
10. Euler’s theorem: $v-e+f=2$ for a planar graph.
11. Using Euler characteristic and handshaking lemmas to prove something about planar graphs
12. Determining the chromatic number of a graph (with proof)
13. Determining the chromatic index of a graph (with proof)
14. The deletion-contraction equation for chromatic polynomials
15. The chromatic polynomial is a polynomial.