1. ## Graph Theory

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.

2. Maybe you can use the handshaking lemma for this. Recall that $\sum\limits_{v \in V} {d(v)} = 2e$, where $d(v)$ is the degree of a vertex $v$. Since the graph is r-regular and has n vertices, then we have $nr=2e$. But if $n$ and $r$ do not divide $e$ (at the same time). Then $nr$ does not divide $e$. This is a contradiction. Thus either $n$ or $r$ must divide $e$.