Decision 1: graph theory

Here are two worked examples from a textbook and I don't understand why the answers are so different.

The first question:

A simple graph G has six verticles 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.

Textbook's solutions

a) 'The sum of all the edges = 13d + 2, therefore d must be even'. I assume this is because the sum of all degrees in a graph is even but then why does that not apply to the second question (see below)?

b) 'As the graph is simple 3d-1 < 5, therefore d < 2. As d = 0 is impossible, d = 2.' I think I understand this except why is it 3d-1<5 instead of <6?

The second question:

A simple graph, G, has five vertices and each of the vertices has the same degree d.

a) State the possible values of d.
b) If G is connected, what are the possible values of d?
c) If G is Eulerian, what are the possible values of d?

Textbook's solutions

a) 'As there are five vertices d<5, therefore d = 0, 1, 2, 3 or 4.' I don't understand why d can be an odd value here (unlike in question 1) as that would mean the sum of all the degrees would not be even? And why can d be 0 when in the previous question it said d=0 is impossible?!

c) 'As the graph is Eulerian, d cannot equal 3, therefore d= 2, 4.' Why can't it equal 3?

Thanks for any help and sorry if the layout is confusing.

(edited 9 years ago)

Reply 1

ghostwalker

Original post by TheWantedGuy

Yes, 13d+2 must be even.

b) 'As the graph is simple 3d-1 < 5, therefore d < 2. As d = 0 is impossible, d = 2.' I think I understand this except why is it 3d-1<5 instead of <6?

Yes, it should be 3d-1<6, so d < 7/3. And since d must be even, and it can't be zero, then it must be 2.

IF you had 3d-1<5, then d < 2 and you can't then have d=2. Their answer contradicts itself.

The second question:

A simple graph, G, has five vertices and each of the vertices has the same degree d.

a) State the possible values of d.
b) If G is connected, what are the possible values of d?
c) If G is Eulerian, what are the possible values of d?

Textbook's solutions

a) 'As there are five vertices d<5, therefore d = 0, 1, 2, 3 or 4.' I don't understand why d can be an odd value here (unlike in question 1) as that would mean the sum of all the degrees would not be even?

d is restricted to the range 0 to 4 by virtue of the graph being simple on 5 vertices.

It is further restricted by the sum of the vertices being 5d which must be even, so the only possible values for d are 0,2,4.

The given answer is wrong, IMHO.

And why can d be 0 when in the previous question it said d=0 is impossible?!

d=0 was impossible in the first question as one vertex had degree 3d-1, which would be -1 if d was zero, and that's not possible.

c) 'As the graph is Eulerian, d cannot equal 3, therefore d= 2, 4.' Why can't it equal 3?

Thanks for any help and sorry if the layout is confusing.

It can't be 3 as this would mean you have vertices of odd degree, and hence no Eulerian circuit is possible.

This is rather a poor question, IMO, since we can deduce initially that d can't be odd, and they seem to have ignored that fact for the sake of the later parts.

Decision 1: graph theory

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you