0
$\begingroup$

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.

  • 0
    That's a good counterexample. Thanks.2011-11-20

1 Answers 1

1

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$.