unique한 bipartite matching의 성질

한 쌍의 정점을 잇는 간선은 최대 하나이고(no parallel edges),

모든 정점을 포함하는 매칭이 존재하는 이분그래프 G=(L, R, E)가 있다고 하자.

"이 그래프의 최대 매칭이 유일하다면 degree가 1인 정점이 항상 존재한다."에 대해 참/거짓을 밝히고자 한다.

모든 정점을 포함하는 매칭이 존재하므로 모든 정점의 degree는 1 이상이다.

G=(L,R,E)의 모든 정점이 degree가 2 이상이라고 하자.

여기서 서로 다른 매칭이 두 개 이상 존재한다는 것을 보이자.

alternating path와 비슷한, 'alternating cycle'을 생각하자.

alternating cycle이란, 그 간선들이 '매칭된 간선'과 '매칭되지 않은 간선'을 번갈아가는 사이클이다.

예)

1-2

 x

3-4

이런 그래프가 있고, 매칭은 {1-2, 3-4}일 때,

1-4-3-2-1 이 alternating cycle의 예이다.

1-4 : 매칭안됨

4-3 : 매칭됨

3-2 : 매칭안됨

2-1 : 매칭됨

이러한 alternating cycle을 찾으면 우리는 바로 증명 완료!이다.

매칭된 간선들을 모두 매칭 안된, 사이클의 이웃한 간선들로 바꾸면 되기 때문이다.

다른 간선들은 영향을 받지 않는다.

위의 그래프에서는 {1-2, 3-4} 대신에 {1-4, 3-2}로 바꿀 수 있는 것이다.

alternating cycle은 항상 존재할까?

원래 그래프를 생각해보자.

|L|=|R|=N 라고 하면,

L에 속하는 모든 정점에 대해 두 개 이상의 간선이 연결되어있기 때문에 |E|≥2N 이다.

그러면 G는 정점이 2N개, 간선이 2N개 이상인 그래프이다.

이러한 그래프는 트리의 성질에서 '반드시 사이클이 존재한다'!

(사이클이 없다면, 서로 연결되지 않은 여러 트리들의 집합이다.

이 경우, 간선은 2N - (트리들의 갯수) 개만큼 존재해야 한다.)

여기서 alternating cycle이 존재할까?