티스토리 뷰

Theorem. 그래프 $G$가 이분그래프임과 $G$가 홀수 길이의 사이클을 포함하지 않음은 동치이다.

 

Proof. 

$G$가 이분그래프이면 홀수 길이의 사이클을 포함하지 않음은 명백하다.

$G$가 홀수 길이의 사이클을 포함하지 않는다고 하자. $G$가 여러개의 컴포넌트로 이루어져 있다면, 각 컴포넌트를 따로 고려해주면 된다. 따라서, $G$가 연결그래프임을 가정할 수 있다.

이제, $G$가 연결그래프이므로, $G$의 spanning tree $T$를 잡을 수 있다. $T$ 상의 아무 정점에서나 시작해서 dfs를 하며 2-coloring을 해줄 수 있다. 만약, $G$의 어느 간선이 색이 같은 두 정점 $u, v$를 잇는다면, $T$ 상의 $u, v$를 잇는 경로와 해당 간선으로 이루어진 사이클은 길이가 홀수이므로 모순을 얻게된다.

따라서, $G$가 $T$ 상의 컬러링을 bipartition으로 하는 이분그래프가 되므로 증명이 종료된다.

 

 

'수학 > 이산수학' 카테고리의 다른 글

이분그래프가 될 조건  (0) 2019.09.06
고정된 크기의 클릭의 수  (0) 2018.04.11
Projective Plane의 Blocking Set의 크기  (0) 2018.02.03
라틴 직사각형 확장  (0) 2018.01.02
2N개의 점들  (0) 2018.01.01
그들 사이의 거리  (0) 2017.09.18
댓글
댓글쓰기 폼
공지사항
Total
20,231
Today
24
Yesterday
25