# Thread: Degrees with sequences finding simple graphs on 5 or 6 vertices

1. ## Degrees with sequences finding simple graphs on 5 or 6 vertices

. For each of the following sequences, find out if there is any simple graph on 5 or 6 verticessuch that the degrees of its vertices are given by that sequence.
If you claim that there isno such graph, provide an argument supporting this claim, otherwise draw a graph with thecorresponding degree sequence.

5 vertices 6 vertices

(a) 5; 3; 2; 2; 2 (d) 5; 5; 3; 2; 2; 1

(b) 3; 3; 3; 3; 2 (e) 5; 1; 1; 1; 1; 1

(c) 3; 3; 3; 2; 2 ( f) 3; 3; 3; 3; 0; 0

(a) 5+3+2+2+2 = 14/5 = 2 and 4/5 (d) 5+5+3+2+2+1 = 18/6 =3
(b) 3+3+3+3+2 = 14/5 = 2 and 4/5 (e) 5+1+1+1+1+1 = 10/2 = 5
(c) 3+3+3+2+2 = 13/5 = 2 and 3/5 (f) 3+3+3+3+0+0 = 12/6 = 2

Am I right in saying that (a) ,(b) , (c) ,(d) ,(e) are not simple graphs as they have odd edges after they are summed and divided ? and f can be a simple graph as its edges are even.
If i am missing something please let me know
thanks

2. ## Re: Degrees with sequences finding simple graphs on 5 or 6 vertices

The sum of the degrees must be even. So, (c) is out because it would need 6.5 edges and it is not possible to have half an edge.
The maximum degree in a graph is one less than the number of vertices. So, (a) is out because the first vertex only has four other vertices it can be adjacent to, not five.
For (d), if the first vertex has a degree of 5, it means that it is adjacent to every other vertex, so that accounts for a degree of 1. For the second vertex, it is also adjacent to every vertex, which would mean that the final vertex must have a degree of at least 2. So, that graph is not possible, either.
For (b), (e), and (f), these graphs are possible.

(b) vertex set = {a,b,c,d,e}. Edge set = {(a,c),(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}. The degree of a vertex is the number of distinct pairs containing the vertex. So, d(a) = |{(a,c),(a,d),(a,e)}| = 3, d(b) = |{(b,d),(b,e)}| = 2, d(c) = |{(a,c),(c,d),(c,e)}| = 3, d(d) = |{(a,d),(b,d),(c,d)}| = 3, d(e) = |{(a,e),(b,e),(c,e)}| = 3. So, the degrees are 3,3,3,3,2 (because the convention is to order degrees from greatest to least).

(e) is a star (one vertex in the middle surrounded by five vertices. every surrounding vertex has an edge going to the center vertex, so it looks like a star)

(f) is a complete graph on four vertices with two unconnected vertices off to the side.

3. ## Re: Degrees with sequences finding simple graphs on 5 or 6 vertices

That is amazing ,
I wish all you people were here while I was doing this math ,
I spend hours trying to understand all of this ...and with your help can hopefully achieve to pass my course ,last semester I learnt calculus for the first time and although not the greatest mark I passed with helpful advice from this site .
Truly grateful ...
Thanks SlipEternal I will try and learn how you came up with the results .
cheers