kiiten
Badges: 18
Rep:
?
#1
Report Thread starter 4 years ago
#1
Please could someone help me with this graph theory question.

EDIT: See last post

I need help on the circled questions.

Name:  Screenshot 2017-05-12 08.07.34.png
Views: 399
Size:  48.4 KB
0
reply
Kevin De Bruyne
Badges: 21
Rep:
?
#2
Report 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.

Name:  Screenshot 2017-05-12 08.07.34.png
Views: 399
Size:  48.4 KB
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
reply
kiiten
Badges: 18
Rep:
?
#3
Report Thread starter 4 years ago
#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
Attached files
0
reply
kiiten
Badges: 18
Rep:
?
#4
Report Thread starter 4 years ago
#4
Bump

Tagging some people who have helped me in the past with D1
0
reply
ithinkitslily
Badges: 16
Rep:
?
#5
Report 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
reply
kiiten
Badges: 18
Rep:
?
#6
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#7
Report 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
reply
kiiten
Badges: 18
Rep:
?
#8
Report Thread starter 4 years ago
#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?
I asked about bii not cii?

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

rearranging gives me n = 3 which is correct
0
reply
ithinkitslily
Badges: 16
Rep:
?
#9
Report 4 years ago
#9
(Original post by kiiten)
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
0
reply
kiiten
Badges: 18
Rep:
?
#10
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#11
Report 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
reply
kiiten
Badges: 18
Rep:
?
#12
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#13
Report 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
reply
kiiten
Badges: 18
Rep:
?
#14
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#15
Report 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
reply
kiiten
Badges: 18
Rep:
?
#16
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#17
Report 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
reply
kiiten
Badges: 18
Rep:
?
#18
Report Thread starter 4 years ago
#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
reply
ithinkitslily
Badges: 16
Rep:
?
#19
Report 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
reply
kiiten
Badges: 18
Rep:
?
#20
Report Thread starter 4 years ago
#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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All