Let G be a r-regular graph on n vertices with e edges. Prove one of n or r must divide e.
The only thing that I can think of to apply to this problem is that a r-regular graph has every vertex at r degrees.
Thanks in advance!!
Maybe you can use the handshaking lemma for this. Recall that $\displaystyle \sum\limits_{v \in V} {d(v)} = 2e$, where $\displaystyle d(v)$ is the degree of a vertex $\displaystyle v$. Since the graph is r-regular and has n vertices, then we have $\displaystyle nr=2e$. But if $\displaystyle n$ and $\displaystyle r$ do not divide $\displaystyle e$ (at the same time). Then $\displaystyle nr$ does not divide $\displaystyle e$. This is a contradiction. Thus either $\displaystyle n$ or $\displaystyle r$ must divide $\displaystyle e$.