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!

$\endgroup$
2
  • 1
    $\begingroup$ Hint: It's in the name... (one example at least where $n=4$) $\endgroup$
    – Dan Rust
    Mar 23, 2015 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, 2015 at 16:26

1 Answer 1

Reset to default
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$)?

$\endgroup$
7
  • $\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, 2015 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, 2015 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, 2015 at 18:21
  • $\begingroup$ en.wikipedia.org/wiki/Cycle_graph $\endgroup$
    – StevenClontz
    Mar 24, 2015 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, 2015 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.