그래프이론(Graph Theory)문제를 해결해 보겠습니다. 문제는 아래와 같습니다.
Use induction to prove that if a graph does not have an odd cycle then it is bipartite.
odd cycle이 없는 graph는 bipartite 라는 얘기인데요. 이번 글에서는 이 문제를 풀어보겠습니다.
참고할만한 글:
- [그래프이론(Grpah Theory)] Prove that the Petersen graph has no cycle of length 7.
- [그래프이론(Graph Theory) 문제풀이] Find all simple graphs with n vertices having no isolated vertex and no induced subgraph with exactly two edges.
- [그래프이론(Graph Theory) 문제풀이]Let P and Q be be paths of maximum length in a connected graph G. Prove that P and Q have a common vertex.
- [그래프이론 문제풀이] Let u and v be adjacent vertices in a simple graph G. Prove that uv belongs to at least d(u) + d(v) − n(G) triangles in G.
- [그래프 이론(Graph Theory)-1] k-set과 k-subset
그래프이론(Graph Theory)
이번 글에서 풀어야 하는 문제는 아래와 같습니다.
Use induction to prove that if a graph does not have an odd cycle then it is bipartite
저는 귀납법을 이용해서 문제를 풀이 하겠습니다. 귀납법을 사용하기 위한 명제를 아래와 같이 정의하겠습니다.
P(n): odd cycle 을 갖지 않는 vertex가 n개인 graph 는 bipartite 이다.
이제 증명을 하겠습니다.
n=1 일 때 odd cycle을 갖지 않는 graph 는 single tone 이므로 bipartite 입니다.
n=2 일 때 odd cycle을 갖지 않는 graph 는 loop가 없는 graph 이므로 bipartite 입니다.
P(n)을 참이라고 가정합시다. vertex가 n+1 개인 graph G를 생각해봅시다. 일반화를 잃지 않기 위해 G는 connected라고 해봅시다. Maximal path P 를 생각하고 P를 구성하는 vertex의 끝점 u를 생각합니다. 그리고 G-u 에 대해 생각해봅시다. 귀납적인 가정에 의해 G-u 는 bipartite 이고 bipartition A,B를 갖습니다. u와 adjacent한 vertex가 A또는 B한곳에만 있다는 것을 보이겠습니다. 만약에 A에 속하는 vertex x가 있고 B에 속하는 vertex y가 있고 x,y둘다 u와 adjacent 하다고 가정합시다. u는 maximal path의 끝점이므로 x와 y는 모두 maximal path P위에 있습니다. 따라서 x와 y는 connected 이고 P위에서 x와 y를 잇는 path Q의 vertex는 B와 A를 번갈아가면서 나오기 때문에 Q의 길이는 홀 수 입니다. 그렇게되면 u-Q-u 라는 cycle이 만들어지고 이 cycle이 odd가 됩니다. 따라서 u는 A의 vertex 들하고만 adjancent하거나 B의 vertex들하고만 adjacent해야 합니다.
문제출처- 광주과학기술원 최정옥 교수님의 “그래프 이론” 수업 (2023년 가을학기) 중 Homework 2