Question regarding bipartite graphs and their subgraphs.

Show that a graph $G$ is bipartite iff every subgraph $H \subseteq G$ contains a set $X \subseteq V(H)$ of pairwise non-adjacent vertices such that $|X|\geq \frac{|V(H)|}{2}$.

Is there a property of subgraphs of a bipartite graph that would help me in this proof? I have found a similar question here, but it was about linearly independent groups of vertices, a concept which I haven't learned yet. Any explaination is welcome.

$"\implies"$: Let $G$ be bipartite. Then there are bipartitions $A$ and $B$ such that the points in respectively $A$ and $B$ are pairwise non-adjacent. For every subgraph $H$ assign the vertices $V(H)$ to either $A$ or $B$. Let these sets of vertices be $A_H$ and $B_H$ respectively. Since $A$ and $B$ are bipartitions of $G$, it follows that $A_H \cup B_H=V(H)$. If $|A_H|=|B_H|$, let $X=A_H$. It follows that $|A_H|=|B_H|=\frac{|V(H)|}{2}$. If $|A_H|\neq|B_H|$, let $X$ be the one with greater cardinality. It follows that $|X|\geq \frac{|V(H)|}{2}$, since $A_H$ and $B_H$ are disjunct.

$"\impliedby"$: Let it be true that for every subgraph $H \subseteq G$ there exists a set $X\subseteq V(H)$ of pairwise non-adjacent vertices such that $|X|\geq \frac{|V(H)|}{2}$.

Consider all vertices $v_i \in V(G)$ and two sets $M_1, M_2$.

• Move all vertices from $V(G)$ to $M_1$ and let $M_2$ be empty.
• Run through all $v_i \in M_1$ . For a fixed $v_i$, run through all $v_j, j \neq i$. If $v_i$ and $v_j$ are adjacent, move $v_j$ to $M_2$.

After running through all $i$, all vertices in $M_1$ are pairwise non-adjacent.

Now we make all pairs of vertices in $M_2$ non-adjacent. For that I use the assumption I made about existence of $X$.

• Run through all $v_k \in M_2$. For a fixed $v_k$ consider a $v_{m} \in M_1$ such that $v_k$ and $v_m$ are adjacent ($v_m$ exists since $v_k$ has been moved to $M_2$ due to this connection). Now run through all $v_n \in M_2$ and consider the subgraph $H$ with $V(H)=\{ v_k, v_m, v_n \}$. For a fixed $v_n$ we now use the assumption, $|X|=2$, since $v_k, v_m$ are adjacent. Now it follows that $X=\{v_k, v_n\}$, the pair in $M_2$ is non-adjacent or $X= \{v_m, v_n\}$, implying that the pair in $M_2$ is adjacent.
• If $X= \{v_m, v_n\}$ is the case, swap $v_m$ and $v_k$. The $v_k$ will remain in $M_1$, since $M_2$ contains a $v_n$ which is adjacent. Move all $v_i \in M_1$ which are adjacent to $v_k$ to $M_2$. We now know that since $v_n, v_k$ are adjacent, any $v_i$ we moved to $M_2$ is non-adjacent with all elements in $M_2$, considering $V(H)=\{ v_k, v_i, v_n \}\implies X=\{v_i, v_n\}$ for any $v_n \in M_2$.

After we have two disjunct sets of vertices such that no pair of vertices is adjacent in each set. Thus we have created bipartitions on $V(G)$ and thus $G$ is bipartite.

• Assuming that $V(X)$ is the number of vertices of the graph $X$, what you say is false: since for every $H$ we may chose $V(H)$ as $X$, it follows that every graph is bipartite. You need some conditions on that $X$. – Leo163 Dec 18 '16 at 16:47
• My fault, I have missed out a crucial point in the question. Thank you. – B.Swan Dec 18 '16 at 16:50
• can you add it? – Jorge Fernández Hidalgo Dec 18 '16 at 17:12
• There is a contidion for $X$, the vertices in $X$ must be pairwise not connected. – B.Swan Dec 18 '16 at 17:32

Your answer in the $\implies$ direction isn't complete. You've only shown the property for $G$ and not every subgraph of $G$. Luckily a set intersection argument is all that is needed to show that every subgraph of a bipartite graph is bipartite and hence your argument holds for all subgraphs.
In the other direction, note that a graph $G$ is bipartite if and only if it contains no odd cycles. Assume that $G$ contains an odd cycle. Then the subgraph $X$ consisting of that odd cycle does not fulfill your condition that at least half of its vertices are non-adjacent.
Hence by the contrapositive of my previous statement, if every graph $X$ does fulfill that condition then we have no odd cycles and $G$ is bipartite.
• What was to prove in $\implies$ is the existence of $X$ with the noted properties. I have shown that for any $H$ by creating $A_H$ and $B_H$. – B.Swan Dec 22 '16 at 10:17