1
$\begingroup$

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!

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Jimbo_ai Mar 24 '15 at 18:15
  • $\begingroup$ 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$. $\endgroup$ – StevenClontz Mar 24 '15 at 18:20
  • $\begingroup$ ...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? $\endgroup$ – Jimbo_ai Mar 24 '15 at 18:21
  • $\begingroup$ en.wikipedia.org/wiki/Cycle_graph $\endgroup$ – StevenClontz Mar 24 '15 at 18:21
  • $\begingroup$ Oh thanks a lot!!! I found the solution thanks to your help...I am grateful! Thank you very much... $\endgroup$ – Jimbo_ai Mar 24 '15 at 18:26

Your Answer

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

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