Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

Question

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph is 5-colorable. It's rather simple to prove Five Color Theorem in a standard mathematical approach (without resort to computers) and many graph theory textbooks explain this proof based on induction. (Even the wikipedia article covers the proof.)

Now, I'm interested in an algebraic proof of Five Color Theorem using chromatic polynomials. Let $\pi_G(x)$ be a chromataic polynomial of a graph $G$. The Five Color Theorem is proved once $\pi_G(5) > 0$ is shown for any planar graph $G$ because $\pi_G(5)$ is the number of 5-colorings of a graph $G$. In fact, Birkhoff introduced the chromatic polynomial with the hope of proving the Four Color Theorem by showing that $\pi_G(4) > 0$ for any planar graph. This approach was in vain, yet he and Lewis succeeded in showing that $\pi_G(x) > 0$ for any planar graph $G$ when $x$ is a real number larger than or equal to 5. For this algebraic proof of Five Color Theorem, many people point to 97-page paper written by Birkhoff and Lewis in 1946.

---

As a computer science TA of an advanced graph theory course, I think this algebraic proof is worth for a brief explanation and may be an adequate thesis topic for master student or even an undergraduate student. But it's somewhat hard to find out which part of the 97 page document is about an algebraic proof of Five Color Theorem. (Probably it's because I'm not a native speaker and not familiar with paper writing styles almost 70 years ago.)

1. Is there anyone who already read Birkhoff and Lewis and can tell me which section is about the actual algebraic proof?
2. Is there any other recent lecture notes or textbooks explaining this algebraic proof in a concise fashion?

Answer 1

I tried to go through Birkhoff and Lewis many years ago but it is not easy because they use different variables and the style is so different to modern proofs.

In modern terms, the key idea is that if a graph contains a vertex $v$ of degree k, then you can get an expression of the form $$P(G,\lambda) = (\lambda-k) P(G-v,\lambda) + \text{other terms}$$ where the other terms are all chromatic polynomials of minors of $G$.

So if the inductive hypothesis is that $P(G,x)> 0$ for all $x\geq 5$, then this reduction gives the inductive step.

Then we know that any planar graph has a vertex of degree at most 5, and that a minor of a planar graph is planar, and so we're done.

The expression involving $(\lambda-k)$ was proved by Thomassen, separately by Woodall, and more generally for all matroids by Oxley whose result preceded the others by two decades. However, although he proved the result, Oxley didn't actually state it explicitly, so missing it can be excused.

I'll dig out the BL paper tomorrow and see if their approach was essentially the same.

Added I think that the result is contained in Theorem 3.1 on page 413 in the BL paper (freely available from AMS), which bounds the coefficients of a polynomial $Q$ (the chromatic polynomial after a few trivial factors are removed). They helpfully remark that in this chapter, their usage of the symbol $\ll$ is "contrary to the notation of the preceding chapter", presumably to prevent any complacency on the part of the reader.