I have a problem where, when trying to solve it, I use some parts which would prove that a k-connected graph contains a k-connected bipartite subgraph. I am fairly sure that this can not be correct, does someone see how my approach is wrong or is this implication true?
The proof for the statement would look somewhat like that: Take a $k$-connected graph $G$ and a bipartite subgraph $H$ of $G$ that is maximally-connected. Assume it is not $k$-connected, thus there is a set of vertices $C$ in $H$ with $c:=|C|<k$ where $H-C$ is not connected. Because the removal of $C$ disconnects $H$, there are two vertices $x, y$ in $H$ that are the only vertices connected to $C$. Because $H$ is bipartite and there exists a path of length 3 from $x$ to $y$, $x$ and $y$ are in the same partition $A$ and $C$ is contained in $B$.
Because $G$ was $k$-connected, there was a subset $C'$ in $G \backslash H$ with $|C\cup C'|=k$ and $C\cup C'$ disconnects $G$ and which is also connected to $x$ and $y$. Because the vertices in $C'$ are no longer connected to $x$ and $y$ (otherwise $H$ would be $|C\cup C'|=k$-connected), we have that $C'\subset A$.
This means that we can reconstruct $H$ by moving the vertices of $C'$ to $B$ and reconnecting $C'$ to $x$ and $y$, thus increasing the connectivity of $H$ to $|C \cup C'|=k$, which contradicts the maximality of the connectivity of $H$.
Again, does someone see where my proof is wrong or is my assumption correct?
Best Answer
There is a much simple counterexample though. Take any odd-length cycle [such as a 3-cycle]--which is 2 connected. What must every bipartite subgraph be.