홀의 결혼 정리 (Hall's Marriage Theorem)

gazelle-and-cs.tistory.com/10

en.wikipedia.org/wiki/Hall%27s_marriage_theorem

 

이분그래프 $G=(L+R, E)$에서, $L$의 부분집합 $S$에 대해 이와 연결된 $R$의 부분집합을 $N(S)$라 하자.

 

이 이분그래프에서 L의 모든 정점이 참여하는 매칭이 존재할 필요충분조건은 모든 $S$에 대하여 $|S| \leq |N(S)|$ 가 성립하는 것이다.