Connectivity of bipartite graph

Question

We consider $G$ to be a bipartite graph that is $(d \geq 1)$-regular and has at most $4d-1$ vertices. We wish to show that $G$ must be connected.

My thinking was to prove by contradiction. So $G$ has at least two components, all of which are bipartite, so are of the form $(A_i,B_i)$ for $A_i,B_i \subseteq V(G)$ in which all $A_i$ and $B_i$ are pairwise distinct.

Since each vertex has degree $d$, then the number of edges in $(A_i,B_i)$ is $d|A_i| = d|B_i|$.

I am stuck from here, I was wondering what the next step may be to determine our contradiction on the number of vertices to prove the statement.

Answer 1

You are close! You should count the number of vertices instead of the number of edges.

Consider a vertex in $A_i$. Since it has degree $d$, we need at least $d$ vertices in $B_i$. Now, consider a vertex in $B_i$. Since it has degree $d$, we need at least $d$ vertices in $A_i$. This gives us at least $2d$ vertices in each connected component.

If there is more than 1 connected component, we will get at least $4d$ vertices.