定理3.1 让d>=3, 和图G中所有顶点的邻居数目<=d, 以及图G不含有d+1度的clique。那么，图G一定是d色可染。
Note: 我们给一个图G“染色”是指，对每个顶点染上一个颜色，并且使得相邻的两个节点颜色不同。d色可染，是指只用d种颜色就能给这个图G染色。
证明：假设定理不成立，那么存在一个图G，是所有违反该定理的图中，顶点数目是最少的。在继续证明之前，必须注意到：让C是一个颜色集合，并且C能给G染色。让S是C的一个子集，我们说G(S)是“图G通过S颜色induce出来”的子图，即是剔除C-S颜色染的那些顶点以及它们相邻的边从而得到的子图。那么对于G(S)中任意的一个“connected component”，“重新分配”它们的颜色，这样出来的结果对于G来说仍旧是一个染色。“重新分配”是指对于染了a颜色的顶点，全部替换成b颜色，染了b颜色的顶点，全部替换成a颜色。
我们接着证明以下几个引理，从而证明出该定理。
引理3.1.1 图G一定存在一个节点x，x的邻居数目是d。
证明：如果所有的节点的邻居数目都是<= d - 1，那么去掉任意一个节点y后图G就变成了图H，由于图G是“最小”的d色不可染的图，图H一定是d色可染。假定图H现在用了一种d-染色，那么图G中y的d-1个邻居只会有d-1种颜色，这样y就可以染上剩下的一种颜色，从而使得图G是d色可染的，产生了矛盾。证毕。
有了引理3.1.1，不难看出对于一个有d个邻居的节点x，图G去掉x后产生的图H一定是d色可染，并且任意一种图H的d-染色一定会使得x的d个邻居x_1, ..., x_d都染成了不同的颜色。否则的话，如果x的d个邻居只用了d-1种颜色，那么x染上剩下的一种，那么G又变成了d色可染了。我们假定x_i节点染的颜色是i , i = 1, 2,..., d.
引理3.1.2 由i, j两种颜色induce出来的子图H_ij中，x_i 和 x_j 一定是连通的。
证明：如果x_i 和 x_j 不连通，那么它们就分属两个不连通的“connected component”。然后随便“重新分配”其中一个component的颜色，我们会得到一个新的图H的染色，但这个染色使得x_i 和 x_j 同色了，和引理3.1.1的推论相矛盾，证毕。
由于x_i和x_j是连通的，记它们所在的连通部分为C_ij.
引理3.1.3 C_ij一定只是一个简单路径，即是C_ij中只存在一条路径连通着x_i和x_j ， 并且这条路径上的中间节点的邻居数目=2.
证明：如果从x_i到x_j有两条路径，就意味着x_i有两个邻居是染了j颜色的，那么x_i在H中的所有邻居一定只有d-2种颜色，因为x_i在图H中最多只有d-1个邻居（在图G中最多d个邻居，而图H又踢掉了x）。那么我们就可以重新对x_i染色，这和引理3.1.1的推论相矛盾。
现在证明引理的后半部分。让个节点y是x_i -- x_j 路径上第一个拥有邻居数目 >= 3的。那么这三个邻居节点在图H中一定是同色的，y在图H中的所有邻居最多只染了d-2种颜色，y就可以重新染让一个既不是i也不是j的颜色，从而使得x_i 和 x_j 就不再是连通的了，证毕。
引理3.1.4: C_ij 和 C_ik 只能相交在节点x_i 上。
证明：如果C_ij 和 C_ik 还能相交在另一个节点z上，那么由于z在C_ij上，所以z有两个邻居都是j颜色。同理z也有两个邻居是k颜色。那么z在H中的所有邻居最多只染了d-2种颜色（除上述4个邻居外，剩下d-4个邻居最多染了d-4种颜色，加上4个邻居的两种颜色）。那么z在H中就可以重新被染上一种不属于x, y, k的颜色，又产生了矛盾，证毕。
有了引理3.1.4，现在来完成这个定理的证明。由于定理中假设了不存在d+1的clique，那么x_1, x_2, ..., x_d这d个点，一定存在一对节点，比如x_1和x_2，是不相邻的。现在让a是x_1的邻居，并且染上了颜色2，那么a就在C_12中。现在我们“重新分配”C_13中的颜色，记染色后新的x_i --- x_j 路径为 D_ij. 显然a在D_23上，因为原来的x_1被染上了颜色3，而a又是染上了颜色2。同时，a也在D_12上，因为a被染上的是颜色2。这样D_12和D_23相交在了节点a上，和引理3.1.4相矛盾。定理证明完毕。