홀의 보조정리는 결혼 정리로도 알려져 있으며, 매칭이 존재하는지 확인해야 하지만 그것을 명시적으로 구성할 필요는 없는 문제에서 매우 편리한 판정 기준입니다.
홀의 보조정리. 완전 매칭이 존재할 필요충분조건은 왼쪽 부분의 임의의 정점 집합이 그보다 적지 않은 수의 오른쪽 부분 정점과 연결되어 있는 것입니다.
증명. 한쪽 방향은 자명합니다. 완전 매칭이 존재한다면, 왼쪽 부분의 정점들의 임의의 부분집합에 대해 그 부분집합과 매칭으로 연결된 오른쪽 부분의 정점들을 취하면 됩니다.
반대 방향은 더 어렵습니다. 귀납법을 사용해야 합니다. 매칭이 완전하지 않다면 이러한 그래프에서 증가 경로를 찾을 수 있고, 이를 이용해 매칭의 크기를 1만큼 늘릴 수 있음을 증명하겠습니다.
귀납의 기저: $L$의 정점 하나이며, 이 정점은 조건에 따라 $R$의 정점 적어도 하나와 연결되어 있습니다.
귀납 단계: $k < n$번의 단계 후에 매칭 $M$이 구성되었다고 합시다. $M$에 매칭으로 포화되지 않은 $L$의 정점 $v$를 추가할 수 있음을 증명합시다.
정점 집합 $H$를 생각해 봅시다. 이는 오른쪽 파트에서 왼쪽 파트로는 매칭의 간선만을 따라, 왼쪽 파트에서 오른쪽 파트로는 아무 간선이나 따라 이동할 수 있을 때 $x$에서 도달 가능한 모든 정점입니다(사실상 쿤 알고리즘에서 증가 경로를 찾을 때 이러한 그래프를 만듭니다)
그러면 $H$에는 매칭에 의해 포화되지 않은 $R$의 정점 $y$가 존재합니다. 그렇지 않고 그러한 정점이 없다면, 정점 $H_L$(매칭에 의해 포화된 왼쪽 부분의 정점들)을 고려할 때 이들에 대해 $|H_L| \leq |N(H_L)|$이라는 조건이 성립하지 않게 됩니다(여기서 $N(X)$는 $X$와 매칭으로 연결된 정점들의 집합입니다).
그러면 $x$에서 $y$로 가는 경로가 존재해야 하며, $R$에서 $L$로는 항상 매칭의 간선만을 따라 이동했으므로 이 경로는 매칭 $M$에 대한 증가 경로가 됩니다. 이 경로를 따라 교대를 수행하면 더 큰 매칭을 얻으므로, 귀납 가정은 참입니다.