3
$\begingroup$

The question in my assignment is

“Draw a simple graph with $6$ vertices, and $8$ edges that contains exactly one cycle of length $4$ and two cycles of length $3$.”

I can draw a simple graph with $6$ vertices and $8$ edges but it doesn’t contain exactly one $4$-cycle and two $3$-cycles, sometimes there is one $5$-cycle in the graph as well.

Any ideas how can I construct a simple graph as the requirement said? Thank you.

Update So I attempted to draw a graph as presented below enter image description here

From what I noticed A>B>F>E>A is a 4-cycle. A>D>E>A and B>C>F>B are 3-cycles. However, in the graph, A>B>C>F>E>A is a cycle of length 5 and A>B>C>F>E>D>A is a cycle of length 6. So, there are other cycles in the graph with cycle lengths are more than 3 and 4. Am I understanding this in the correct concept or not?

$\endgroup$
1
$\begingroup$

Since you've drawn your example in the plane, cycles contain faces, so we can readily check it's correct: it has exactly two $3$-cycles and exactly one $4$-cycle. Any other cycle contains some faces, and must have length greater than $4$.

I ran a Nauty script to generate the 6-vertex 8-edge graphs, and manually checked which have exactly two 3-cycles and exactly one 4-cycle. These are the three possibilities up to isomorphism:

enter image description here

Yours is the example in the middle.

In the first two examples, we have faces surrounded by 3, 3, 4, and 5 edges. Combining any two faces gives a cycle of length 5 or more.

In the third example, we have faces surrounded by 3, 3, 5, and 5 edges. There's a 4-cycle around the combined 3-edge faces. Combining faces in any other way, gives a cycle of length 5 or more.

$\endgroup$
0
$\begingroup$

The trick is to plan around the cycles you want instead of just randomly connecting vertices.

So, the 4-cycle and two 3 cycles are a rectangle and two triangles. That's 4+2*3=10 vertices and similarly 10 edges. So, to do it in with 6 and 8 you need to share 2 edges and 4 vertices between the cycles. There's multiple ways to do this and correspondingly multiple solutions, but the simplest is just to connect each triangle to the square along an edge (since that then shares two vertices and an edge, twice).

$\endgroup$
2
  • $\begingroup$ Is it correct? The graph I drew above. $\endgroup$ Apr 26 '18 at 9:28
  • $\begingroup$ @Maninthemiddleattack yes your graph is correct. The question doesn't say to not have cycles of greater length, it just tells you how many cycles to have of lengths 3 and 4. $\endgroup$ Apr 26 '18 at 22:21
0
$\begingroup$

The best you can do with $6$ vertices and $8$ edges is to have exactly two $3$-cycles and exactly one $4$-cycle, as you have. That must be all the question is asking. You can't also avoid having longer cycles (proof below).

You need the cycles to overlap, otherwise there isn't enough room to fit them all in. So there is one edge in two cycles. Remove this, leaving a connected graph with $7$ edges. If there were exactly three cycles to start with, there would be only one left. Remove any edge from that cycle to break it. What you have left has no cycles, so has to be a tree, but it has too many edges ($6$ rather than $5$). This is a contradiction, so any $6$-vertex $8$-edge graph has at least four cycles.

$\endgroup$
2
  • 1
    $\begingroup$ Thank you for the clarification, but how do I apply this concept to build a graph with edges of 8 since your presented graph is only contains 7 edges. $\endgroup$ Apr 26 '18 at 8:57
  • $\begingroup$ Oops, I can't count, sorry! In that case it is impossible. I'll edit my answer. $\endgroup$ Apr 26 '18 at 9:40

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.