How would I show that a k-regular bipartite graph G (say it can be partitioned into S and T) has an even number of vertices? Would I try to show that the number of vertices in S equals the number of vertices in T and therefore it is an even number of vertices?
Here is my attempted proof: (please let me know if this is valid reasoning or if I messed up, I am still a little confused about this)
I know the sum of the degrees of the vertices of S equals the sum of the degrees of the vertices of T. The sum of the degrees of the vertices of S is also the number of edges in G so I could say if S has p vertices then the total number of edges in S divided by k is equal to p. The same applies to T. Therefore the number of vertices is even.
Best Answer
Because $G$ is a regular graph, each vertex of $G$ has exactly $k$ edges. Suppose $S$ and $T$ are the two parts of the bipartite graph $G$, with $n_1$ and $n_2$ vertices respectively. Because $G$ is bipartite, the number of edges in $G$ must equal $n_1k$ and $n_2k$, which means that $n_1=n_2$. Therefore the total number of vertices in $G$ is $n_1+n_2=2n_1$, an even number.