Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By SlipEternal

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

  1. #1
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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

    My answers :

    (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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,837
    Thanks
    1089

    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.
    Thanks from bee77
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2017
    From
    Annabay
    Posts
    198

    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. non-isomorhpic simple graphs with four vertices
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 26th 2014, 07:02 PM
  2. Replies: 8
    Last Post: Aug 17th 2013, 03:45 AM
  3. Graphs & Degrees
    Posted in the Algebra Forum
    Replies: 6
    Last Post: Aug 5th 2012, 05:52 PM
  4. Proove Graphs and vertices
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 7th 2009, 11:57 PM
  5. Vertices of a simple graph
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jun 8th 2007, 03:37 PM

/mathhelpforum @mathhelpforum