Results 1 to 2 of 2

Math Help - Non-isophermic graphs

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    14

    Non-isophermic graphs

    Construct all non-isomorphic simple connected graphs on 8 vertices with 19 edges, at least one maximal degree vertex and at least one pendant vertex. Prove they are not isomorphicand that there are no more.

    I ran out of ideas to do a graph with the conditions required in the question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1

    Graphs

    Hello smithhall
    Quote Originally Posted by smithhall View Post
    Construct all non-isomorphic simple connected graphs on 8 vertices with 19 edges, at least one maximal degree vertex and at least one pendant vertex. Prove they are not isomorphicand that there are no more.

    I ran out of ideas to do a graph with the conditions required in the question.
    Here's a graph that satisfies the conditions to get you started. The vertices are A_1...A_8, with degree as follows:

    A_1:7 (maximum)
    A_2:6
    A_3:6
    A_4:6
    A_5:4
    A_6:4
    A_7:4
    A_8:1 (pendant)

    The sum of the degrees of the vertices is 38, because there are 19 edges, each edge connecting 2 vertices.

    To construct a second graph that's not isomorphic to this one, you could re-draw this one by removing the edge (A_4, A_7) and replacing it by the edge (A_5, A_6). This will produce the following specification:

    A_1:7 (maximum)
     A_2:6
     A_3:6
     A_4:5
     A_5:5
     A_6:5
     A_7:3
     A_8:1 (pendant)

    I suspect there aren't many other possibilities.

    Grandad
    Attached Thumbnails Attached Thumbnails Non-isophermic graphs-untitled.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graphs
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: March 3rd 2010, 06:54 AM
  2. Graphs
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 2nd 2010, 08:25 PM
  3. Replies: 0
    Last Post: December 29th 2009, 08:08 PM
  4. graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 29th 2007, 04:15 AM
  5. Help with graphs
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: October 20th 2007, 10:03 PM

Search Tags


/mathhelpforum @mathhelpforum