임의의 스패닝 트리 T를 하나 정했을 때, (파란색 간선의 개수가 최대/최소를 넘어서지 않는 범위에서는) 언제나 파란색 간선의 개수+1/-1인 새로운 스패닝 트리 T'을 만들 수 있다 하면 증명에 충분합니다.

여기에 추가로, +1이 가능한 것만 증명하면 -1은 색깔을 반전시키면 같은 증명으로 가능합니다. 이제 +1이 가능함을 증명합시다.

-----

0.모든 파란색 간선만을 이용해 그래프를 만들어 봅시다. 이 그래프가 x개의 connected component를 가지고 있다고 합시다. 이때, 파란색 간선의 최대 개수는 n-x개임도 알 수 있습니다.

1.임의의 스패닝 트리 T에 속한 파란색 간선만을 사용해 그래프를 만든다면, 0에서 구한 "x개의 connected component"가 좀 더 잘게 쪼개진 형태일 것입니다.

2. (1)에서 component가 쪼개졌다면=즉 현재 파란색 간선이 최대가 아니라면, 반드시 T에 속하지 않는 파란색 간선 E_b이 존재하여, 하여금 (1)에서 쪼개진 어떤 두 component를(A와 B라고 합시다) 다시 이을 수 있습니다.

3. (2)에 이어서: T에서 A와 B를 연결하는 경로 위에 있는 있는 어떤 빨간색 간선 E_r이 존재해야 합니다. T에서는 A와 B가 연결되어 있지만, 파란색 간선만으론 연결되어 있지 않기 때문입니다.

4. 이제 E_r를 제거하고, E_b를 추가하면, 스패닝 트리는 유지되고, +1에 성공합니다. 증명 끝!