Theory of Computation proof by construction of graph

Question

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?

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.

But:

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