哈德維格-納爾遜問題 哈德維格納爾遜問題英語HadwigerNelson problem是指在平面上為每點填色最少要多少種顏色才能使若兩點距離為其顏色必定不相同呢用圖論的語言可這樣敍述設G為圖G的頂點是平面上的所有點兩個頂點相鄰若且唯若它們在平面上的距離為求G的點色數這個問題等於求任意G的有限子集的最大點色數 這個問題的下界是上界是 只有三種顏色無法完成的證明如下平面上任取一點A設其顏色為x以其為圓心分別以和  displaystyle sqrt  為半徑做圓在半徑  displaystyle sqrt  的圓上任取一點B以其為圓心為半徑做圓交以A為圓心為半徑的圓與C和D則C與D的距離為所以ACD顏色必須各不相同設CD的顏色分別為yzBCD的顏色也必須各不相同所以B的顏色只能是x所以以A為圓心  displaystyle sqrt  為半徑的圓上所有的點的顏色都必須為x在其上選擇兩個相距為的點它們的顏色相同與題設矛盾 另一方面將平面劃成以外接圓直徑略少於的正六邊形密鋪以七種顏色填上使得一個正六邊形和相鄰的六個正六邊形的顏色不同這樣的密舖符合距離為的點顏色不相同所以上界是