Is there a 5-regular graph of order 7?

Question

How can I decide if there is a 5-regular graph of order 7?

Some hints or tips would be appreciated. This question arises in studying for a graph theory course.

Answer 1

It is not possible to have such a graph. More generally, it is not possible to have a $d$-regular graph on $n$ vertices for $d$ and $n$ odd.

To see this recall (or convince yourself) that for $e$ the number of edges in a $d$-regular graph on $n$ vertices you have $2e=nd$.

Answer 2

Suppose $G$ is a $5$-regular graph of order $7$. Let $\bar G$ be the complementary graph: same vertices, but two vertices are joined by an edge in $\bar G$ just in case they are not joined by an edge in $G$. Can you see that $\bar G$ is a $1$-regular graph of order $7$? Is that possible? Try to draw it.

Answer 3

Hint: Do you know a theorem that says something about the number of vertices of odd degree?