I was reviewing some lectures notes and noticed that in a proof of a theorem our lecturer stated that the "sides" of a k-regular bipartite graph are equal and that it is trivial to prove it. Anyway I've been trying to prove it but I'm not to sure about my answer.
Ok so this is my try with a proof by contradiction :
Let G(V=A $U$ B, E) be a k regular bipartite graph, Need to show that $|A|$ = $|B|$.
Let $|A|$ = n and $|B|$ = m. Let n $!=$ m. lets say n $>$ m ( could be other way around) since the graph is k regular we need to "distribute" k*n edges from A to B, but since n > m there will always be a vertex in B with a degree of at least k+1. contradiction
Not to sure about the this proof, sorry about the English
Thanks!
Your proof is fine, though one could simplify it (i.e. there is no need to do a proof by contradiction): As you write, the number of edges in the graph equals $nk$. It also equals $mk$. Hence $nk=mk$ and $(n-m)k=0$. We conclude that $n=m$ or $k=0$. As a matter of fact, your proof also makes use of $k\ne 0$ (can you see why?). Actually, reading your proof does not make this immediately apparent, which indictes that you may add a bit more detail to the point where you conclude that onenode must have degree $\ge k+1$.
But that is not simply a problem of the proof, in fact it is alreeady a problem of the claim: A $0$-regular grpah with an odd number of vertices is inde3ed bipartite! - For the corrected claim, however, the proof is quite fine .