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.

  • $\begingroup$ 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$. $\endgroup$ – Leo163 Dec 18 '16 at 16:47
  • 1
    $\begingroup$ My fault, I have missed out a crucial point in the question. Thank you. $\endgroup$ – B.Swan Dec 18 '16 at 16:50
  • $\begingroup$ can you add it? $\endgroup$ – Jorge Fernández Hidalgo Dec 18 '16 at 17:12
  • $\begingroup$ There is a contidion for $X$, the vertices in $X$ must be pairwise not connected. $\endgroup$ – 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.

  • $\begingroup$ 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$. $\endgroup$ – B.Swan Dec 22 '16 at 10:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.