D1 help :S

Please could someone help me with this graph theory question.

I need help on the circled questions.

What have you tried for a?

I think you didn't get enough sleep... which is really important during exam time. And in general...

Please post your attempt for a) at least. You should be trying to attempt questions and posting your working to get the maximum benefit from getting help.

Why do you think i didnt get enough sleep?

I always attempt questions before posting, i just forget to attache my working- here it is.

Posted from TSR Mobile

part a) is correct - on the mark scheme it is drawn differently (your answer and the corrected answer are isomorphic graphs)

c iii) for a eularian graph, all vertices must have an even order, and for a complete graph all vertices must have an order of n - 1, so what does this tell you about n?

iv) consider what is needed for a eularian cycle and a hamiltonian cycle, and that the graph is a completed graph. (hint: try to equate two things and you will end up with n = 3)

c)iii so eulerian graphs have odd vertices?

iv) eulerian has n(n-1) / 2 edges and not sure about hamiltonian.

Any ideas with bii) ?

yes for c)iii

iv) hamiltonian cycles will have an equal amount of edges as vertices

c)ii since the graph is complete, what is the order of all of the vertices?

I asked about bii not cii?

c)iv) Oh so n(n-1) / 2 = n

rearranging gives me n = 3 which is correct

sorry mistyped,what i said is still relevant for b)ii lol

Even order?

Just to be sure are we talking about the same question - "why K8 is not eulerian"?

yes,
it has 8 vertices and is a complete graph, which always have an order of n - 1

So it doesnt have an odd number of vertices?

Why does the mark scheme say "odd number of edges at vertices"? - what does that mean?

it has 8 vertices. it is a complete graph, which means that each edge has an order (number of edges connected to it) of 7 (n - 1).
eulerian graphs must have even orders at all the vertices, therefore this graph cannot be eulerian.

How do you know its a complete graph when youre only given the number of vertices?

Im confused

Posted from TSR Mobile

at the top it says Kn is a complete graph, so K8 will also be a complete graph

Ah yeah sorry - didnt read the ques properly. Thanks

Just to be sure complete graphs with n vertices have an order or n-1 at each vertex.

Eulerian graphs have even order at each vertex (n-2??)

Posted from TSR Mobile

yes to the first part
for eulerian graphs all vertices do have an even order, however that should probably be donated by an order of 2n (with there being 2n + 1 vertices)

Wait im confused. So if a eulerian graph has n vertices what is the order of the vertices in terms of n?

there is no specific number for the order of a vertex in a eulerian graph - they just all have to have an even order.

however, in a complete graph the n vertices will have an order of n-1

if a graph is complete and eulerian it must have 2n + 1(an odd number) vertices, each with an order of 2n (an even number, 1 less than the number of vertices)