Lecture 8

We saw a typical example of a proof using the pigeonhole principle. Specifically, any set of n+1 integers between 1 and 2n (inclusive) contains a pair of distinct integers, one of which divides the other.

We look at three tasks related to graph isomorphism:

• proving that two graphs are isomorphic
• using differences in local features to show that two graphs are not isomorphic
• counting the number of isomorphism from a graph to itself

We then looked at two problems that use "two-way bounding": marker making and graph coloring.