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 , where is the degree of a vertex . Since the graph is r-regular and has n vertices, then we have . But if and do not divide (at the same time). Then does not divide . This is a contradiction. Thus either or must divide .