My Favorite Graphs

Lyrics by Jeff Erickson
Music by Rogers and Hammerstein
("My Favorite Things" from The Sound of Music)

Trees have no cycles but must be connected.
Tourn'ments are cliques with their edges directed.
Hamilton circuits, Eulerian paths,
These are a few of my favorite graphs.

Matchings and bicliques and blossoms and bases,
Kempe chains, hypercubes, forests, and faces,
AKS networks that split into halves,
These are a few of my favorite graphs.

Short paths of co-authors leading to Erdös,
Large neural networks that translate from Kurdish,
Finite projective planes - they make me laugh.
These are a few of my favorite graphs.

Chorus:

Propositions, corollaries,
Problems that are starred,
I simply remember my favorite graphs
And then they don't seem so hard.

If there's no K5 or K3,3 minor,
Old Kuratowski says it'll be plinor.            (Excuse me... planar.)
Four's enough colors if there are no gaffes!
These are a few of my favorite graphs.

Minor-closed families and sparsifications,
Voronoi diagrams found on giraffes,
These are a few of my favorite graphs.

Chorus:

Propositions, corollaries,
When they're just too deep,
I simply remember my favorite graphs
And then I go right to sleep.

[Several months after I finished this, er, masterpiece, I started writing another Sound of Music math filk, called "How Do You Solve a Problem by Induction?" ("... How do you go from n to n+1?") But I stopped as soon as I remembered that The Sound of Music already has an induction song!]

Here are more filkified "Favorite Things":

Hacking/hackish:
• "Circular MAPCAR and ANDCA'd negation..."
• "Compaqs and Lisas and hard disks with tape drives..."
• "Foobars on bazes, and quuxes on sillys..."
• "Lambdas and closures and interneral defines..."
• "Pointers to pointers to printf()-like functions..."
• "Recursion, self-reference, and reiteration..."
• "This routine sets up some pointers to functions..."
X-files:
• "Agents and Bagels and Cream cheese for snacking..."
• "Big Blue and Queequeg and Jose and Yappi..."
• "Strange lights that hover above air force bases..."
• "Tear drops on your nose from journals I've written..."
Other science fiction:
• "Arrogant scientists, robotic ponies..."
• "Daleks are planning, with Davros their leader..."
• "Giant green monsters that visit from Mars..."
• "Khakis and jumpsuits gave way to nice leather..."
• "Microns and hectares and novas and centons..."
SCA:
• "Tourneys that start late and courts that are too long..."
• "Yesterday morning the Duke was a-screaming..."
Other:
• "Crystals and braziers, exotic incenses..."
• "Dissecting puppies and torturing kittens..."
• "Fourteen inch [censored] with straps of elastic..."
• "Men in black leather with tempting tight arses..."
• "Sharp knives and strong knives and Emasculators..."
• "Shiny blue dresses and choc-flavoured icing..."

• Jeff Erickson (jeffe@cs.uiuc.edu) 29 Nov 2001