Let $G$ be a bipartite graph with $n$ vertices. Prove that if every vertex has degree at least $\frac{n}{4} + 1$, then $G$ is connected.
I'm assuming that number of vertices in this bipartite graph must be divisible by 4, not sure where to go from there.
Best Answer
Let the two parts of the graph be $A$ and $B$ if it is not connected then it contains $k\geq2$ connected components. Each of these connected components contains at least $\frac{n}{4}+1$ vertices in $A$ and at least $\frac{n}{4}+1$ vertices in $B$. So each connected component has at least $\frac{n}{2}+2$ vertices. So if we have $k$ connected components we need $\frac{kn}{2}+2k$ vertices, even for $k=2$ we get $n+4$ vertices. So it is impossible for $G$ to be disconnected.