# Components of a k-regular bipartite graph

Let $G$ be a $k$-regular bipartite graph and let $A$ and $B$ be its partitions. Let $C$ be a component of $G$ and let $C_A = C \cap A$ and $C_B = C \cap B$. I want to prove that $C=K_{k,k}$. Since $G$ is $k$-regular, every vertex in $C_A$ has $k$ neighbors in $C_B$, so $k \le |C_B|$. Similarly $k \le |C_A|$. Now suppose $k < |C_B|$. I am not sure where to go from here.

• I am not sure, but I think you get a counterexample by considering a hexagon, a connected 2-regular bipartite graph with $|A| = 3 = |B|$. – Matthias Klupsch Nov 20 '11 at 16:26
• That's a good counterexample. Thanks. – echoone Nov 20 '11 at 16:58

The claim is equivalent to "the only $k$-regular graphs $G$ are the union of disjoint $K_{k,k}$ subgraphs".
Suppose we have a $k$-regular bipartite graph with $k \geq 2$ formed by the union of $2$ or more disjoint $K_{k,k}$ subgraphs. Suppose $AB$ is an edge in one $K_{k,k}$ and $CD$ is an edge in another $K_{k,k}$. Then we can delete these edges, and replace them by $AD$ and $CB$. This gives a $k$-regular bipartite graph with a component that does not satisfy the claim (it has $2 \times 2k$ vertices, but only $2k^2$ edges).
So, the claim is true if and only if $k=1$.