ChapterZero

I enjoyed my Graph Theory class today, immensely. First, we completed two proofs that I understood, in their entirety, in a relatively organized and through manner! The first was that planar graphs always have a minimum degree less than 5. The second was the Kempe 5 color theorem– that every planar graph has a chromatic number less than or equal to 5. The proof for the first consisted of a fairly routine application of Euler’s Theorem and a new and clever application of triangulations (the fact that any graph can be extended into a triangulation, and in the process degrees of the vertices are only increased). Clever by my account, but the second was unbelievably cool. It is one of those proofs that I would learn an entire branch of math to be able to understand (luckily in this case I didn’t need to). And one I hope someday to equal. Awesome proof, really. I wish I could explain it here… maybe someday I will.

The very last thing we did in class was talk about an interesting application of graph theory to computer science, in particular the construction of space optimizing compilers. That is, let the vertices of a graph G be the variables used in your program, and define adjacency as the fact that the live intervals of the variables (the period during which they hold values), overlap. Then the chromatic number of the graph indicates the number of registers necessary to satisfy the memory requirements of your program, assuming each variable fits in a register. Now tell me that isn’t an ingenious application of graph theory!

Possibly relevant posts:

• spectral graph theory and two CS applications (5/4/2008)
• Planarity of a bipartite graph (10/1/2007)
• More lattice stuff (2/18/2005)