그래프 G가 bipartite면 G는 홀수 cycle을 가지지 않는다. (bipartite) / Graph Theory #2

graph theory

A graph is bipartite iff it has no odd cycle.

위의 정리를 이해하려면 bipartite graph가 무엇인지 알아야 한다. 정의는 다음과 같다.

A graph G is bipartite if V(G) is the union of two disjoint (possibly empty) independent sets.

정의가 한 번에 이해가 되지는 않는다. 자세히 풀어보면, 그래프 G의 vertices가 두 개의 disjoint independent sets의 합집합이라고 한다.