그래프 G에서 각 v∈V에 대해 색의 집합 C(v) (|C(v)|=k)가 어떻게 주어져도 이웃한 꼭짓점의 색이 다르도록 각 v가 C(v)의 한 색으로 색칠 가능한 k의 최솟값을 χ_l(G)라 한다. 그리고 C(v)들이 모두 같을 때 이웃한 꼭짓점의 색이 다르도록 색칠 가능한 k의 최솟값을 χ(G)라 한다.
연결되었으며 경계가 있는 모든 면이 세 변을 갖는 평면그래프를 유사삼각하다고 하자.
그리고 ‘색칠’을 ‘이웃한 두 꼭짓점의 색이 다른 색칠’이라는 뜻으로 사용하겠다.
H가 G의 부분그래프라면, χ(H)≤χ(G)이다. 따라서 유사삼각그래프에 대해서만 증명하면 증명이 완성된다.
1. u,v∈B, u−v∉B인 u,v가 존재할 때 이 때 \\{x,y\\}=\\{u,v\\}이거나 u−v를 기준으로 x,y가 같은 방향에 있게 된다. 전자의 경우 x−y를 기준으로 나뉘어진 두 부분그래프가 색칠 가능하므로 G 또한 색칠 가능하다. 그리고 후자의 경우 우선 u−v에 의해 나뉘어진 두 부분그래프 중 x−y가 포함된 부분그래프를 색칠한 후 반대쪽 부분그래프를 색칠하면 (u,v가 색칠된 상태이므로 가정의 1번 조건을 만족하여 색칠 가능하다) G의 색칠이 완료된다. 부분그래프의 색칠가능성은 귀납가설에 의해 보장된다.
2. 위와 같은 u,v가 존재하지 않을 때 v_0를 B 위에서 x를 기준으로 y 반대쪽에 있는 점이라고 하고, v_0와 이웃한 점들을 x,v_1,v_2,⋯,v_n,_z (v_i∈V∖B, z∈B)라 하자. |C(v)|≥3에서 |C(v)∖\\{α\\}|≥2이므로 γ,δ∈C(v)∖\\{α\\}, γ≠δ인 γ,δ가 존재한다. 이제 G에서 v_0과 연결된 변들을 제거하고, C(v_i)를 C(v_i)∖γ,δ로 바꾸어 새로운 그래프를 만들자. 귀납가설에 의해 이 그래프는 색칠 가능하다. 다시 v_0를 추가하고, γ,δ 중 z의 색이 아닌 것으로 v_0를 색칠하면 G의 색칠이 완료된다.
