Getting started on graph theory and I'm stuck on an exercise.
I'm supposed to find a graph that has cycles of lengths 5,6,7,8,9 but nothing else, with 10 vertices tops.
I swear I've been stuck on that for 20 minutes now. Is there a technique or just trial and error. (I'm at the very beginning of the book so I don't know much except basic definitions)
I did find a graph with cycles of 5,6,8,9 but it seems like trying to get that 7 would make a <5 cycle. Anyone?
>>9060283
are you sure the question does not ask for a directed graph?
No one?
It's a pain being a graphcel, the Konigsberg problem took me a whole 20 minutes to solve.
>>9060305
>Draw a connected graph having at most 10 vertices that has at least one
cycle of each length from 5 through 9, but has no cycles of any other length
should have specified, it's a connected graph.
what's a directed graph?
>>9060313
each arc is one-way. it's impossible to make such a graph if all the arcs are bidirectional and you only have 10 nodes.
>>9060343
I don't know, that's a copy/paste of how the problem is stated, it's in the first few pages of a well known book.
>>9060351
What book is this from? This certainly does not seem like a beginner exercise.
If 7 was missing it would be a good way to get you to learn properties of the Petersen graph but as it is I don't understand how a beginner could be intended to approach this.
>>9060357
Combinatorics and Graph Theory, by Harris, Hirst and Mossinghoff
looks like a complete beginner's book, they start with the bridge problem and everything
yeah without the seven it's pretty easy.
You sure it's impossible?
Why is that?
>>9060283
assume an undirected graph.
suppose your graph has a cycle of length 9. this requires a minimum of nine vertices, right?
you're left with one vertex. if it connects two existing nodes, what's the shortest path between them? it must be no greater than four. if the vertex does not connect at least two nodes, you're not making any new cycles.
>>9060283
Jesus Christ OP, this literally took me 5 minutes.
>>9060406
you got it. i forgot to add the length of the edges cause by the extra node.
>>9060431
* the edges.
>>9060397
>it must be no greater than four.
see, it's this shit right here. why did my brain hand give me that obviously incorrect information?
not op, btw.
>>9060406
I had that exact same graph but I don't see a cycle with length 7. Maybe I have the wrong definition of what a cycle is.
>>9060513
A cycle is a path where the last vertex is adjactent to the first vertex
>>9060513
Fuck I just saw it I feel fucking stupid.
>>9060513
>>9060566
Yeah I just saw it, after 10 minutes. I shoudl get some sleep.
For some reason I was seeing literally every cycle but this one.
brainlet life