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 .