We had this assignment in our class and I was also provided with the solution. I want to ask about a small detail in it.

The assignment:

Proof by construction. For each even number $n$ greater than or equal to $4$, there exists a $3$-regular graph with $n$ nodes.

The solution:

The set of nodes of $G$ is $V = 1, 2, ..., n$

And the set of edges of $G$ is the set $E = \{(i, i + 1) | i = 1, 2, ..., n-1\} \cup \{(n, 1)\} \cup \{(i, i+n/2)| i = 1, 2,..., n/2-1\}$

My question: Why does the set $\{(i, i+n/2)| i = 1, 2,..., n/2-1\}$ have the $-1$ in it? For example if $n=8$ we would need to have an edge $(4, 8)$ in our graph, right? But that cannot happen because the highest possible i in that set would be $3$. Or does the $(4, 8)$ come from somewhere else?


1 Answer 1


You are right, there shouldn't be a $-1$.

We can verify that the $E$ given cannot be $3$-regular by using the degree-sum formula:

$$3 \times n = 2E$$

so there should be $3n/2$ edges.


$$|E| = (n-1)+1+n/2-1=3n/2-1 < 3n/2$$

  • $\begingroup$ The formulas you mentioned are helpful. I will be sure to use them in the future. $\endgroup$
    – lulabee
    Sep 11, 2020 at 20:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .