Constructing a 3-Regular Graph with No 3-Cycles
$\Begingroup$ 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...
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?
2 Answers
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$?.
Maya is a hardware enthusiast who tests and reviews smart home devices, smartphones, wearables, and audio gear. She focuses on practical consumer value and build quality.
