2
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.