Lesson 2

As is often the case, to solve the problem it's useful to first consider its simple special cases: this both develops intuition and helps with later generalization.

• For the empty graph \(G=\overline{K_n}\) on \(n\) vertices, we have \(P_{G}(x)=x^{n}\): each of the \(n\) vertices can be colored with any of the \(x\) colors.


• For the complete graph \(G=K_{n}\) on \(n\) vertices, we have \(P_{G}(x)=x(x-1)\dotsb(x-n+1)\): the first vertex can be colored with any of the \(x\) colors, the second—with any of the \((x-1)\) remaining colors, and so on.


• For the path graph \(G=P_{n}\) on \(n\) vertices, we have \(P_{G}(x)=x(x-1)^{n-1}\): the first vertex can be colored with any of the \(x\) colors, and each next vertex—with any of the \((x-1)\) colors (only the color of the adjacent vertex is forbidden).

from networkx import chromatic_polynomial

print(chromatic_polynomial(nx.empty_graph(4)))
print(chromatic_polynomial(nx.complete_graph(4)))
print(chromatic_polynomial(nx.path_graph(4)))

x**4
x**4 - 6*x**3 + 11*x**2 - 6*x
x**4 - 3*x**3 + 3*x**2 - x