이 글에서는 이분 그래프에서 매칭을 찾는 알고리즘의 핵심이 되는 보조정리 하나를 증명하겠습니다. 하지만 그 전에 몇 가지 개념을 더 도입해야 합니다.
길이가 $k$인 체인(chain)이란 정확히 $k$개의 간선을 포함하는 어떤 단순 경로(즉, 반복되는 정점이나 간선을 포함하지 않는 경로)를 말합니다.
어떤 매칭에 대하여, 간선이 번갈아 가며 매칭에 속하고/속하지 않는 길이 $k$의 단순 경로를 교대 체인이라고 부릅시다.
어떤 매칭에 대하여 시작 정점과 끝 정점이 매칭에 속하지 않는 교대 경로를 증가 경로라고 부르겠습니다.
이름에서 알 수 있듯이, 증가 경로를 이용하면 매칭의 크기를 1만큼 늘릴 수 있습니다. 이를 위해 그러한 경로를 하나 잡아 교대를 수행하면 됩니다. 즉, 경로에 속한 간선 중 매칭에 포함된 간선을 모두 매칭에서 제거하고, 그 대신 경로의 나머지 간선을 모두 매칭에 추가합니다.
증가 경로에는 모두 홀수 개의 간선이 있으며, 첫 번째 간선과 마지막 간선은 매칭에 속하지 않았습니다. 교대 후에는 영향을 받은 각 정점이 반대쪽 파트의 정점 정확히 하나와 연결됩니다. 따라서 교대 후에도 매칭은 올바르게 유지되며, 그 크기는 정확히 1만큼 증가합니다.
위 예시에서는 파란색 간선 $(1, 8)$, $(3, 7)$, $(4, 6)$이 추가되고, 빨간색 간선 $(3, 6)$과 $(4, 8)$은 제거됩니다. 간선 $(2, 5)$에는 아무 일도 일어나지 않습니다. 이 간선은 증가 경로에 속하지 않기 때문입니다. 따라서 매칭의 크기가 1만큼 증가합니다.
증가 경로를 교대시키면 매칭의 크기를 1만큼 늘릴 수 있으므로, 최대 매칭에는 증가 경로가 없어야 합니다. 그 역도 성립한다는 사실이 밝혀져 있습니다.
#베르주 정리
정리. 증가 경로가 없는 매칭은 최대 매칭입니다.
증명은 귀류법으로 하겠습니다. 두 매칭 $|A| \leq |B|$가 있고, $A$에 대한 증가 경로가 없다고 가정합시다. 이 경로를 찾아 $A$를 하나 늘리는 방법을 보이겠습니다.
$A$에 해당하는 매칭의 간선은 빨간색으로, $B$에 해당하는 매칭의 간선은 파란색으로, 두 매칭 모두에 속하는 간선은 보라색으로 칠합시다. 이제 빨간 간선과 파란 간선만으로 이루어진 그래프를 생각해 봅시다. 이 그래프는 사실상 두 매칭의 대칭차이므로, 각 정점에 인접한 간선은 최대 2개입니다. 따라서 이 그래프의 모든 연결 요소는 빨간 간선과 파란 간선이 번갈아 나타나는 경로이거나 사이클입니다. 모든 사이클에는 빨간 간선과 파란 간선이 같은 수만큼 있고, 전체적으로 파란 간선이 더 많으므로 파란 간선으로 시작하고 파란 간선으로 끝나는 경로가 반드시 존재합니다. 바로 이 경로가 $A$에 대한 증가 경로가 되며, 따라서 $A$는 최대가 아니므로 모순이 발생합니다.