문제출처
광주과학기술원(GIST) 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 2
Solution
P(n): A graph with $n$ vertices and no odd cycles is bipartite.
(i). Base step:
- For $n = 1$, a graph with a single vertex is trivially bipartite.
- For $n = 2$, a graph with two vertices cannot have an odd cycle and is bipartite.
(ii). Inductive hypothesis:
Assume $P(k)$ is true for some positive integer $k$.
That is, any graph with $k$ vertices and no odd cycles is bipartite.
(iii). Inductive step:
Consider a graph $G$ with $k+1$ vertices and no odd cycles.
Without loss of generality, assume $G$ is connected.
- Choose a maximal path $P$ in $G$ and let $u$ be an endpoint of $P$.
2. Consider the subgraph $G-u$ - the graph $G$ with vertex $u$ removed. - By the inductive hypothesis, $G-u$ is bipartite. Let $A$ and $B$ be its bipartition.
- We will show that $u$ is adjacent to vertices in only one of $A$ or $B$:
- Assume, for contradiction, that $u$ is adjacent to a vertex $x$ in $A$ and a vertex $y$ in $B$.
- Since $u$ is an endpoint of a maximal path, both $x$ and $y$ must be on $P$.
- $x$ and $y$ are connected, and the path $Q$ from $x$ to $y$ on $P$ alternates between vertices in $A$ and $B$.
- Therefore, the length of $Q$ is odd.
- This creates a cycle $u-Q-u$, which is an odd cycle.
- This contradicts our assumption that $G$ has no odd cycles.
- Therefore, $u$ is adjacent to vertices in only one of $A$ or $B$.
- We can complete the bipartition of $G$ by adding $u$ to $B$ if it's adjacent to vertices in $A$, or to $A$ if it's adjacent to vertices in $B$.
(iv). Conclusion:
By induction, $P(n)$ is true for all positive integers $n$.
Therefore, any graph with no odd cycles is bipartite.
감점이 있었습니다. 해당 문제는 퀴즈에도 출제된 적 있으니 후배님들은 확인해보시길 바랍니다.
- What if G is not a connected graph? e.g. G=(V,null)