How to draw a simple graph with given vertices, edges and number of cycles?

Question

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

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?

Answer 1

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).

Answer 2

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.

Answer 3

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:

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.