# Graph theory haiku

## 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 ^{[1]}. 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).

Short proofs of classical theorems.

*Journal of Graph Theory*44(3). J Adrian Bondy (2003). ↩︎