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 .