Let G be a r-regular graph onnvertices witheedges. Prove one ofnorrmust 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!!

Printable View

- Dec 8th 2009, 04:32 PMzachschGraph 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.

Thanks in advance!! - Dec 8th 2009, 06:52 PMguildmage
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$.