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.


$$|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 '20 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.