In the Fall 2010 semester, I gave a series of three talks in UVic’s discrete math seminar: two on monopolar claw-free graphs and one based on Adrian Bondy’s paper Short Proofs of Classical Theorems. In the last talk, I presented Bondy’s proofs of Vizing’s, Ore’s, and Brooks’ theorems.
For a little bit of fun, I rewrote them in haiku form (tanka in the case of Brooks’ theorem):
Vizing’s Theorem
Induction on n.
Swap available colours
and find SDR.
Ore’s Theorem
A red-blue Kn:
bluest Hamilton circuit
lies fully in G.
Brooks’ Theorem
Greedily colour,
ensuring neighbours follow
all except the last.Choose the last vertex wisely:
friend of few or of leaders.
Slides of the talk can be found here (PDF).