# Constructing a 3-regular graph with no 3-cycles

I have a question that is as follows:

For each integer $n \geq 3$, construct a 3-regular graph on $2n$ vertices such that $G_n$ does not have any 3-cycles.

Here is what I have:

I have $2n$ vertices numbered $1, 2, \ldots, 2n$, and a vertex $k$ connected to $k-1$, $k+1$, and $k+n$. (All three numbers are interpreted $\mod 2n$, so for instance given $n=5$, we would have edges 1-2, 2-3, 3-4, ..., 9-0, 0-1, and 1-6, 2-7, 3-8, 4-9, 5-0).

Now, to conclude my argument, how can I verify that there exist no 3-cycles in this graph?

-
You have $2n$ vertices numbered $1,2,\dots,n$ --- do you mean $1,2,\dots,2n$? –  Gerry Myerson Mar 13 '13 at 3:47
Oops, yes, my bad! –  user41419 Mar 13 '13 at 3:48

What you have described is an example of a circulant graph, and your method will pan out (as per Ross Millikan's answer).

I'd also like to add that there's examples that are not only $3$-cycle free, but have no odd length cycles (i.e., they're bipartite graphs).

If we label the vertices $\{u_0,u_1,\ldots,u_{n-1}\} \cup \{v_0,v_1,\ldots,v_{n-1}\}$ and add an edge from each $u_i$ to $v_i$, $v_{i+1}$ and $v_{i+2}$ (with indices modulo $n$), then we obtain a $3$-regular bipartite graph. (The vertex $v_i$ is adjacent to $u_i$, $u_{i-1}$ and $u_{i-2}$, so it is indeed $3$-regular.)

An example when $n=5$ is given below:

The $2n$-vertex circulant graph examples will have $(n+1)$-cycles, and $n+1$ might be an odd number. For example, when $n=4$ we have a $5$-cycle illustrated below:

There's also another "cheats" way to answer the question. Since the question doesn't specify that the graphs be connected, we can find examples $G_3,G_4,G_5$ for $n=3,4,5$, respectively, then we obtain examples in all cases by taking:

• An arbitrary number of disconnected copies of $G_3$,

• The graph $G_4$ together with an arbitrary number of disconnected copies of $G_3$, and

• The graph $G_5$ together with an arbitrary number of disconnected copies of $G_3$.

Here's a $3$-regular graph on $18$ vertices with no $3$-cycles made from $3$ disconnected copies of $K_{3,3}$:

-

If $k$ is part of a 3-cycle you must have an edge between two vertices that $k$ is connected to. So there would have to be and edge between two of $k-1, k+1, k+n$. Clearly there is no edge between $k-1, k+1$. Can there be an edge between $k+n$ and $k \pm 1$?.

-
No, there cannot, but I'm having trouble writing this "formally". Do I simply write that this is because $k+1$, say, would only have edges between $k$, $k+2$, and $k+(n+1)$, and so $k+n$ is not included? –  user41419 Mar 13 '13 at 3:58
@user41419: that depends on what your audience thinks is acceptable. One could worry that if $n$ is too small you might have (say) $k+2=k+n-1$ since $n=3$ is allowed or because your addition is modulo $n$ you might wrap around. Once you eliminate these you are home. –  Ross Millikan Mar 13 '13 at 4:04