Lesson 3

In the three simplest cases we obtained a polynomial of degree \(n\). Below we will see that, for every graph on \(n\) vertices, this is a polynomial of degree \(n\). Naturally, we expect that the coefficient at \(x^{n}\) will be equal to \(1\): for large \(x\), the value of \(P_{G}(x)\) should behave like \(x^{n}\).

The following formula, called the deletion–contraction formula, helps compute the value of \(P_{G}(x)\) in practice. Recall that for a graph \(G(V,E)\) and its edge \(e \in E\), we denote by \(G \setminus e\) the graph \(G\) without the edge \(e\), and by \(G / e\) we denote the graph \(G\) with the edge \(e\) contracted.

Lemma (deletion–contraction formula).For any graph \(G(V,E)\) and its edge \(e \in E\), we have \[P_{G}(x)=P_{G \setminus e}(x)-P_{G / e}(x) \ .\]

Proof. It is convenient to prove this equality in the following form: \[P_{G \setminus e}(x)=P_{G}(x)+P_{G / e}(x)\ .\] The number on the left is the total number of proper colorings of the graph \(G \setminus e\) in \(x\) colors. All such colorings are split into two classes: those where the ends of edge \(e\) are colored differently (exactly \(P_{G}(x)\) of them), and those where they are colored the same (there are \(P_{G / e}(x)\) of those).◼