今天（2014.7.8）的报告中谈到了图的染色多项式。证明该结果是一个多项式是一个不错的练习。

数学中最常见最简单的关系是线性关系，这是线性代数学习的内容。

然后就属多项式关系，很多有限型问题都能得出多项式的表达式。这是一个经典例子。

一个图\(G\)是一个有限集合。它含有限个点，有限条边。

图\(G\)的一个染色，是把\(G\)的点染色，要求：若两个点之间有边相连，则这两个点染不同的色。

给定图\(G\)，\(k\)种颜色，总共的染色方法数记为\(P_G(k)\).求证：\(P_G(k)\)是\(k\)的多项式。即存在多项式\(f(k)\)使得\(P_G(k)=f(k)\)。

提示：

1. 先算几个简单的图。

2. 给定图\(G\)，把它减掉一条边\(e\)，记为\(G‘=G-e\)，推导\(P_G(k)\)和\(P_{G‘}(k)\)之间的递推关系。