Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 2 down vote accepted

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:

Example when $n=5$

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:

$5$-cycle in the circulant graph example

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

Disconnected copies of $K_{3,3}$

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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