Math 415, Graph Theory and Combinatorics
Fall 2008

Here are a few puzzles:

• Coin weighing problems. The classical puzzle from World War I (used as a weapon):
  Given 12 coins, where one is counterfeit. With a balance scale and three weighings find the fake coin.
• The fifteen game: The puzzle of tiles numbered 1 through 15 in a 4 by 4 square. Can you get them in correct order without removing any of them?
• Instant insanity: Four cubes with four colors on their sides. Can you place them in a tower such that you see all four colors on each side.
• The stable marriage theorem: Can you match n ladies and n gentlemen such that there will be no divorces. (Alternative, match medical residents with hospitals.)

In this course we will learn and apply basic Graph Theory and Combinatorics to solve these types of puzzles. Topics include:

• Basic theory of counting.
• Stirling and Bell numbers. (And a magic trick based upon the fifth Bell number is 52.)
• Eulerian and Hamiltonian paths and cycles in graphs.
• Tree counting.
• Euler's formula for planar graphs.
• The chromatic polynomial of a graph.
• Basic Ramsey theory.
• Permutations.
• Generating functions.

Prerequisite: The new prerequisite is Math 322 or Math 213. (The old prerequisite was CS 101.)
The new course description for the course bulletin. Textbook: A Walk Through Combinatorics, second edition. Miklós Bóna.