Lecture 15

After the examlet, we walked through the details of two proofs by induction:

• the graph coloring theorem from section 11.8
• the Nim game from section 11.10

The color proof is interesting because each step in the induction covers all graphs of a particular size (= number of nodes), not just a single specific graph.

The Nim game is interesting because we have to use the fact that the claim works for a smaller game, but we have very weak control over how much smaller this game is.