Prove that a graph G is bipartite iff every subgraph H of G has anindependent set consisting of at least half of $V(H)$.

문제출처

광주과학기술원-GIST- 최정옥 교수님의 “그래프 이론” 수업, 2024년 가을학기 중 Homework 3

Solution

I will show that both directions are true.

1. Necessary condition:
   If $G$ is bipartite, then every subgraph $H$ of $G$ has an independent set containing at least half of the vertices in $V(H)$.
   • Since $G$ is bipartite, the vertex set $V(G)$ can be divided into two independent sets $A$ and $B$. The subgraph $H$ must have its vertices in $A$ and $B$. That is, $V(H)$ can be divided as $A \cap V(H)$ and $B \cap V(H)$.
   • Both $A \cap V(H)$ and $B \cap V(H)$ are independent sets because there are no edges between any vertices within $A$ or within $B$.
   • Since $G$ is bipartite, the vertex set $V(G)$ is partitioned into two disjoint sets $A$ and $B$, where $V(G) = A \cup B$ and $A \cap B = \emptyset$. The subgraph $H$ also inherits this partition, meaning its vertex set $V(H)$ can be divided as $A \cap V(H)$ and $B \cap V(H)$. Because these two sets are disjoint, the total size of $A \cap V(H)$ and $B \cap V(H)$ must add up to $|V(H)|$, the total number of vertices in $H$.
   • Therefore, at least one of these sets must have a size of $|V(H)|/2$ or larger. If both independent sets $A \cap V(H)$ and $B \cap V(H)$ each have fewer than half of the vertices in $V(H)$, then $|A \cap V(H)| + |B \cap V(H)|$ will be less than $|V(H)|$. This is a contradiction. Since there is no intersection between $A \cap V(H)$ and $B \cap V(H)$, one of these sets must have a size of $|V(H)|/2$ or larger.
   • Thus, either $A \cap V(H)$ or $B \cap V(H)$ is an independent set that contains at least half of the vertices of $V(H)$.
   • Conclusion: The necessary condition holds.
2. Sufficient condition:
   If every subgraph $H$ of $G$ has an independent set containing at least half of $V(H)$, then $G$ is bipartite.
   • Assume that $G$ is not bipartite. This means that $G$ contains an odd-length cycle. A bipartite graph can only have even-length cycles.
   • Let's consider an odd-length cycle $C$ in $G$. Let the number of vertices in $C$ be $2k+1$, where $k$ is a non-negative integer. Thus, $C = (v_1, v_2, \dots, v_{2k+1})$ is a cycle with $2k+1$ vertices.
   • Let's find the maximum independent set in $C$. An independent set is a set of vertices such that no two vertices in the set are adjacent. In $C$, we can construct an independent set by selecting non-adjacent vertices ,e.g., $v_1, v_3, v_5, \dots$. However, because $C$ has an odd number of vertices, after selecting $k$ vertices, the remaining vertex $v_{2k+1}$ will always be adjacent to one of the previously selected vertices (e.g., $v_1$). Thus, $v_{2k+1}$ cannot be included in the independent set.
   • The maximum size of an independent set in $C$ is $k$. This is because we can only select $k$ non-adjacent vertices from $2k+1$ vertices in the cycle.
   • However, $k$ is less than $\frac{2k+1}{2}$. This is a contradiction. The size of an independent set in $C$ is $k$, but for the condition to hold, it should be at least $k+1$, since $\lceil \frac{2k+1}{2} \rceil = k+1$. This means that no independent set in $C$ can contain half or more of the vertices, which contradicts the given condition.
   • Conclusion: Since the assumption that $G$ is not bipartite leads to a contradiction, it follows that $G$ must be bipartite. Thus, the sufficient condition holds.