EXAMINABLE

Question 1

Proofs that ARE examinable

Answer 1

Instant insanity – prove whether or not a set of cubes has a solution

Determine whether or not two graphs are isomorphic, with justification

Prove and apply Euler’s Theorem characterising (semi)-Eulerian graphs

Determine whether or not a graph is (semi)-Hamiltonian “by hand”

Proving the Petersen graph proof is not Hamiltonian

Proving a certain molecule is a tree using handshaking

Proving a Hamiltonian graph isn’t planar using the planarity algorithm (e.g. K_{3,3} or K_5)

Proving a graph isn’t planar using Kuratowski’s theorem

Proving Euler’s Theorem for connected graphs on the sphere

Using Euler characteristic and handshaking lemmas to prove theorems about planar graphs

Determining the chromatic number of a graph (with proof)

Determining the chromatic index of a graph (with proof, using Vizing’s theorem)

Proving the chromatic polynomial is a polynomial (and what the degree and highest two coefficients are)

Determine and apply the chromatic polynomial of a graph (with proof)

Question 2

Instant insanity – prove whether or not a set of cubes has a solution

Answer 2

?

Question 3

Determine whether or not two graphs are isomorphic, with justification

Answer 3

?

Question 4

Prove and apply Euler’s Theorem characterising (semi)-Eulerian graphs

Answer 4

?

Question 5

Determine whether or not a graph is (semi -Hamiltonian “by hand”

Answer 5

?

Question 6

Proving the Petersen graph proof is not Hamiltonian

Answer 6

?

Question 7

Proving a certain molecule is a tree using handshaking

Answer 7

?

Question 8

Proving a Hamiltonian graph isn’t planar using the planarity algorithm (e.g. K_{3,3} or K_5)

Answer 8

?

Question 9

Proving a graph isn’t planar using Kuratowski’s theorem

Answer 9

?

Question 10

Proving Euler’s Theorem for connected graphs on the sphere

Answer 10

?

Question 11

Using Euler characteristic and handshaking lemmas to prove theorems about planar graphs

Answer 11

?

Question 12

Determining the chromatic number of a graph (with proof)

Answer 12

?

Question 13

Determining the chromatic index of a graph (with proof, using Vizing’s theorem)

Answer 13

?

Question 14

Proving the chromatic polynomial is a polynomial (and what the degree and highest two coefficients are)

Answer 14

/

Question 15

Determine and apply the chromatic polynomial of a graph (with proof)

Answer 15

?

Question 16

Algorithms that ARE examinable:

Answer 16

Prufer code and its inverse
Kruskal and Prym
Upper and lower bounds for the traveling salesman problem
Dijkstra’s algorithm for shortest paths
Finding longest paths

Question 17

Proofs we covered that WILL NOT be examined

Answer 17

Ore’s theorem
Cayley’s theorem
Various definitions of trees are equivalent
Kruskal or Prym’s algorithm works algorithm works

Question 18

EXAM STRUCTUREQuestion 1: Introductory matters

Answer 18

In general, this covers everything we did up to when we began algorithms, and is the material in Sections 1 and 2 of the notes.
Questions are almost entirely from the following:
Solving or proving insolvability of Instant insanity cubes
Proving a graph is or is not (semi)-Eulerian i.e., using and proving Euler’s Theorem
Proving a graph is or is not (semi)-Hamiltonian (case by case, a few tricks, proof for Peterson graph)
Definition of a tree, proving trees have leaves, and that a tree on
n
n
vertices has
n−1
n−1
edges
Degrees of vertices, the handshaking lemma, and basic applications to chemistry
Proving two graphs are or are not isomorphic.

Question 19

Question 2: Algorithms

Answer 19

This is section 3 of the notes. Students usually find this the easiest, and in an effort to have more easy points on the exam this section might be slightly easier than past exams, which struggled a bit to find a hard part. Note in revising that Prim’s algorithm only started being covered last year; in previous years only Kruskal’s was covered.
Questions are almost entirely from the following:
Using Prim’s or Kruskal’s algorithm for finding the cheapest weight spanning tree; analysing if there is a unique such tree or more than one
Using Dijkstra’s algorithm for finding shortest paths between points; what happens if we change edge lengths – does the shortest path get longer?
Using the longest path algorithm to find the longest path between points; what happens if we change edge lengths?
Traveling Salesman problem: statement, nearest neighbor greedy algorithm for upper bound, finding lower bounds for TSP by considering spanning trees
Prüfer code: going back and forth from a labelled tree and its code; Cayley’s Theorem that there are
n
n−2
nn−2
labelled trees on
n
n
vertices.
The only algorithm I would ask you to prove works as advertised is the lower bound for the Travelling Salesman problem. In particular, I will not ask you to prove Prim, Kruskal’s or Dijkstra’s algorithm works.

Question 20

Question 3: Graphs on Surfaces

Answer 20

Questions are almost entirely from the following:
Planarity Algorithm for Hamiltonian graphs, in particular proving 
K
3,3
K3,3
and 
K
5
K5
aren’t planar
Kuratowski’s Theorem characterising planar graphs: stating it, and using and proving the “easy” direction, i.e., that if a 
G
G
has a subgraph 
H
H
that’s a subdivision of 
K
3,3
K3,3
or 
K
5
K5
then 
G
G
isn’t planar.
Other surfaces: Drawing graphs on the Mobius band and on the torus. Note: in some previous years there have been questions involving the real projective plane 
RP
2
RP2
or the Klein bottle; we did not cover that this year and it won’t be required
Euler’s Theorem 
v−e+f=2
v−e+f=2
for planar graphs: proving it and using it in applications. A heads up that different years have done different proofs of Euler’s theorem, so solutions given in practice exams may look unfamiliar.

Question 21

Question 4: Colourings

Answer 21

This is Section 5 of the notes.
Questions are almost entirely from the following:
Chromatic number of a graph: definition, determining the chromatic number for a particular graph with proof, proving chromatic number is at most the maximum degree plus one, word problem applications
Chromatic Index of a graph: definition, determing the chromatic index of a particular graph with proof, word problem applications; stating Vizing’s theorem
Chromatic Polynomial: definition, deletion-contraction, proving it’s a polynomial, recovering the chromatic number, number of vertices, number of edges from it.
Calculating Chromatic Polynomial of a graph, using: deletion contraction / induction / gluing along a vertex or an edge