# Theory of Computation proof by construction of graph

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?

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$$

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