# Discrete Mathematics Graphs

I need help about something. I would like to draw a cubic graph (each node has to have degree $3$) $G=(V,E)$, $|V|=2n$, where $n\geq 3$ (it doesn't matter, it can be $3,4,7$ etc). But this graph must not contain triangles. At this point I need your help, while I can not find such a graph. I would appreciate every nominee solution written (or drawn) in any form.

Thank you in advance!

• Hint: It's in the name... (one example at least where $n=4$) – Dan Rust Mar 23 '15 at 16:21
• The above also easily extends to examples where $|V|=8+2k$ for all $k\geq 0$. – Dan Rust Mar 23 '15 at 16:26

## 1 Answer

So, a cycle $C_n$ is $2$-regular, has $n$ vertices, and doesn't have any triangles when $n>3$.

Can you think of a way to join two copies of $C_n$ (giving you $|V|=2n$) so that the result is $3$-regular and contains no triangles (when $n>3$)?

• May you write it in a form of a matrix, if possible, or in any other plausible form in order to make it clear, because I do not actually get your undoubtedly very good suggestion. Thank you very much! – Jimbo_ai Mar 24 '15 at 18:15
• Here's an image of two copies of $C_5$. i.imgur.com/zglbVdJ.png You should be able to add some edges to get the graph you desire. This method should work for $C_n$ for any $n>3$. – StevenClontz Mar 24 '15 at 18:20
• ...and writing cycle Cn you do not mean a circle, do you? You just mean the close path of G with length n and n nodes, right? – Jimbo_ai Mar 24 '15 at 18:21
• en.wikipedia.org/wiki/Cycle_graph – StevenClontz Mar 24 '15 at 18:21
• Oh thanks a lot!!! I found the solution thanks to your help...I am grateful! Thank you very much... – Jimbo_ai Mar 24 '15 at 18:26