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

$\endgroup$ 2

2 Answers

$\begingroup$

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

$\endgroup$ $\begingroup$

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

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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