Thread: 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.



Thanks in advance!!

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 .