일반적으로 전체 점 수가 홀수이면 항상 불가능하고, 짝수이면 항상 가능하다.
일단 그래프에서 변들이 어떻게 색칠되어 있건 간에, i점에 연결된 색칠된 변의 차수를 d_i라 하면 Σd_i=2|E|(E: 색칠한 변 집합)이므로 d_i가 홀수인 점의 수는 항상 짝수이다. 따라서 전체 점 수가 홀수면 불가능.
이제 전체 점 수가 짝수인 경우만 보자. 이 경우 d_i가 짝수인 점의 수는 항상 짝수가 된다.
이제 모든 변들을 색칠한 후, d_i가 짝수인 점들을 둘씩 짝짓자. 그리고 이 그래프에 다음과 같은 시행을 한다;
짝지어진 두 점 x, y에 대해, x에서 y로 가는 경로(path)를 아무거나 하나 찾은 후, 그 경로 위의 변들의 색을 반전시키자(즉, 색칠되었다면 색칠을 지우고, 색칠이 안 되었다면 색칠을 하자.).
이 시행을 하면 x, y에서는 d_i가 1씩 변하나, x, y를 제외한 경로 위의 점들은 d_i가 일정하거나 2씩 변한다.
즉, 시행 전후에 각 점들의 d_i를 생각해 보면 x, y만 d_i의 홀짝성이 바뀌고 나머지 점들은 d_i의 홀짝성이 일정하다. 즉, 매 시행마다 d_i가 짝수인 점 2개가 d_i가 홀수로 바뀐다.
따라서 이 시행을 반복하면 매 시행마다 d_i가 짝수인 점이 2씩 줄고, 처음에 d_i가 짝수인 점의 수는 유한한 값이었으니 이 시행은 반드시 끝나게 된다.
시행이 끝났을 땐 당연히 모든 점의 d_i는 홀수가 되고, 이는 우리가 찾는 배치이니 끝.
- 참조용 그림
참고로 풀이 보면 사실 처음에 시작할 때 꼭 모든 변을 칠하고 시작할 필요는 없음. 그냥 아무거나 몇 개 칠하고(아예 안 칠해도 됨) 시작해도 똑같이 됨.
혹시 이상한 부분 있으면 지적 부탁드립니다
