Graph theory haiku: three short and beautiful proofs

UVic discrete math seminar talk

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).