# D1 help :S

Watch
Announcements
#1
Please could someone help me with this graph theory question.

EDIT: See last post

I need help on the circled questions.

0
4 years ago
#2
(Original post by kiiten)
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.
0
#3
(Original post by Kevin De Bruyne)
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
0
#4
Bump

Tagging some people who have helped me in the past with D1
0
4 years ago
#5
(Original post by kiiten)
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)
0
#6
(Original post by ithinkitslily)
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) ?
0
4 years ago
#7
(Original post by kiiten)
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?
0
#8
(Original post by ithinkitslily)
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?

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

rearranging gives me n = 3 which is correct
0
4 years ago
#9
(Original post by kiiten)

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
0
#10
(Original post by ithinkitslily)
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"?
0
4 years ago
#11
(Original post by kiiten)
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
0
#12
(Original post by ithinkitslily)
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?
0
4 years ago
#13
(Original post by kiiten)
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.
0
#14
(Original post by ithinkitslily)
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
0
4 years ago
#15
(Original post by kiiten)
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
1
#16
(Original post by ithinkitslily)
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
0
4 years ago
#17
(Original post by kiiten)
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)
0
#18
(Original post by ithinkitslily)
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?
0
4 years ago
#19
(Original post by kiiten)
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)
0
#20
(Original post by ithinkitslily)
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)
Ohh so eulerian graphs must have vertices with an order of 2n?
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### What support do you need with your UCAS application?

I need help researching unis (10)
13.89%
I need help researching courses (5)
6.94%
I need help with filling out the application form (4)
5.56%
I need help with my personal statement (30)
41.67%
I need help with understanding how to make my application stand out (18)
25%
I need help with something else (let us know in the thread!) (2)
2.78%
I'm feeling confident about my application and don't need any help at the moment (3)
4.17%