A level decision maths

Hello, I don't understand how to answer questions on simple graphs from the AQA D1 book Chapter 5. If you have the book I am talking about page 92 worked example 5.1, although they give a solution it is not explained and I can't figure it out myself. If you don't have the book but can/ want to help this is the question..

A simple graph, G (not drawn) has six vertices and their degrees are 2d, 2d, 2d+1, 2d+1, 2d+1 and 3d-1 where d is an integer

a) By considering the sum of all the degrees, show that d is even.
b) Use the fact that the graph is simple to show that d<3 and state the value of d.
c) Draw a possible graph G

I REALLY need help with this, thanks!

(edited 9 years ago)

Reply 1

ghostwalker

Original post by Room4student

a) What do you get when you sum the degrees? What do you know about the sum of the degrees of a graph?

b) What's the max possible value for the sum of the degrees? Hence....

c) So, what are the degrees of the vertices, then have a go.

Reply 2

Room4student

Original post by ghostwalker

I understand part b and c it's just a that i'm struggling with. Total order is 13d+2 but I don't know what and how I can deduce things from that, please explain! Also the book says that total number of edges is 13d+2 I think its less because if vertex A and B are joined by an edge than that's just one edge in total not one from A and one from B and therefore 2. Am i wrong? Thanks.

Reply 3

ghostwalker

Original post by Room4student

I understand part b and c it's just a that i'm struggling with. Total order is 13d+2 but I don't know what and how I can deduce things from that, please explain!

Each edge has two ends, it contributes 2 to the total sum of the degrees of the vertices. Hence for any graph, the sum of the degrees of the vertices is always even.

So, 13d+2 must be even.

Also the book says that total number of edges is 13d+2 I think its less because if vertex A and B are joined by an edge than that's just one edge in total not one from A and one from B and therefore 2. Am i wrong? Thanks.

Book's wrong. The sum of the degrees of the vertices is 13d+2, so the number of edges must be half that.

Reply 4

Room4student

Original post by ghostwalker

Each edge has two ends, it contributes 2 to the total sum of the degrees of the vertices. Hence for any graph, the sum of the degrees of the vertices is always even.

So, 13d+2 must be even.

Book's wrong. The sum of the degrees of the vertices is 13d+2, so the number of edges must be half that.

- Thank you I think I understand, d has to be even otherwise 13d+ 2 would be odd and that's impossible. Is it ok to contact you in the future If I ever need any more help with D1, hopefully won't need it though :smile:

- Thought so too, thanks for confirming.

(edited 9 years ago)

Reply 5

ghostwalker

Original post by Room4student

Is it ok to contact you in the future If I ever need any more help with D1, hopefully won't need it though :smile:

- Thought so too, thanks for confirming.

I don't encourage PMs. Always best to post on the forum; others can benefit from the threads, and people are there to check if I get it wrong.

Reply 6

Room4student

Original post by ghostwalker

I don't encourage PMs. Always best to post on the forum; others can benefit from the threads, and people are there to check if I get it wrong.

Ok sure makes sense. I've just come across this question;

A simple graph G has 5 vertices and each of the vertices is of the same degree d.
Question- State the possible values of d.

Solution- as there are five vertices, d<5 therefore d= 0,1,2,3,4

Apologies for asking you another question but it doesnt seem to follow the same rule. Since 5d has to be even I thought d can only be 0 or 2 or 4.

Reply 7

ghostwalker

Original post by Room4student

Solution- as there are five vertices, d<5 therefore d= 0,1,2,3,4

Apologies for asking you another question but it doesnt seem to follow the same rule. Since 5d has to be even I thought d can only be 0 or 2 or 4.

Supplied solution is incorrect. Yes, d must be less than 5, but also, as you realised, it must be even. 0,2,4 are the only possible values.

Edit: As an exercise you might like to try constructing such graphs - you'll run into problems when d is odd.