This is page is some brief commentary on what is examinable vs. what is not. I don’t claim that that this list is exhaustive, but it covers the main proofs we did in class, and most likely anything not appearing on this would be part of the 20% “hard” marks. Please ask if something is missing here and you are unsure, or if something is unclear.

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. Prove and apply Euler’s Theorem characterising (semi)-Eulerian graphs
4. Determine whether or not a graph is (semi)-Hamiltonian “by hand”
5. Proving the Petersen graph proof is not Hamiltonian
6. Proving a certain molecule is a tree using handshaking
7. Proving a Hamiltonian graph isn’t planar using the planarity algorithm (e.g. \(K_{3,3}\) or \(K_5\))
8. Proving a graph isn’t planar using Kuratowski’s theorem
9. Proving Euler’s Theorem for connected graphs on the sphere
10. Using Euler characteristic and handshaking lemmas to prove theorems about planar graphs
11. Determining the chromatic number of a graph (with proof)
12. Determining the chromatic index of a graph (with proof, using Vizing’s theorem)
13. Proving the chromatic polynomial is a polynomial (and what the degree and highest two coefficients are)
14. Determine and apply the chromatic polynomial of a graph (with proof)

Algorithms that ARE examinable:

1. Prufer code and its inverse
2. Kruskal and Prym
3. Upper and lower bounds for the traveling salesman problem
4. Dijkstra’s algorithm for shortest paths
5. Finding longest paths

Proofs we covered that WILL NOT be examined

1. Ore’s theorem
2. Cayley’s theorem
3. Various definitions of trees are equivalent
4. Kruskal or Prym’s algorithm works algorithm works