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?
 A: 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}$:

A: 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$?.
