给定H的任何一个△-着色，我们用表示v的着色i的邻点(=1，…，△) 对i≠j,用H,表示由着色i或j的顶点所导出的H的子图 对于所有i≠j,顶点和U在H的同一个分支C中 (2) 否则，我们可以在其中的一个分支中交换i和j的颜色，从而”和可以着同一 种颜色，与(1)矛盾。 C总是一条-U)路 (3) 确实，令P是C中一条U路，因为dH()≤△-1，所以贴的所有邻点着两 两不同的颜色，否则，我们可以重新给，着色，与(1)矛盾.因此，P上的邻点 也是它在C上的唯一邻点；对u有同样的结论.所以，若C≠P,那么在H中 P包含一个内部顶点，它有三个着同样颜色的邻点，让u是P上第一个这样的顶 点（图5.2.1），因为u的邻点至多用了△-2种颜色，所以我们可以重新给u着色. 但这使得Pu成了H中的一个分支，与(2)矛盾