Use induction to prove that if a graph does not have an odd cycle thenit is bipartite. , Comment: You should first choose which parameter thatyou will apply induction on - number of vertices or number of edges.

문제출처

광주과학기술원(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.

1. 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.
2. By the inductive hypothesis, $G-u$ is bipartite. Let $A$ and $B$ be its bipartition.
3. 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.
4. Therefore, $u$ is adjacent to vertices in only one of $A$ or $B$.
5. 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)