EXAMINABLE Flashcards
Proofs that ARE examinable
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)
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)
?
Algorithms that ARE examinable:
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
Proofs we covered that WILL NOT be examined
Ore’s theorem
Cayley’s theorem
Various definitions of trees are equivalent
Kruskal or Prym’s algorithm works algorithm works
EXAM STRUCTUREQuestion 1: Introductory matters
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 2: Algorithms
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 3: Graphs on Surfaces
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 4: Colourings
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
