Results 1 to 4 of 4

Math Help - A graph theory problem

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1

    A graph theory problem

    How many graphs are there with five vertices, where the degrees of those five vertices are 1,1,2,2,2? I suppose we have to find the number of them up to an isomorphism.

    If we use the theorem stating that the number of edges in a graph is half the sum of degrees of all vertices, we can see that every graph of the type we are looking for will have \frac{1+1+2+2+2}{2}=4 edges.

    I have managed to find only two such graphs:



    In graph G_1, the vertices 1 and 5 are of degree 1, while vertices 2, 3, and 4 are of the degree 2, while in graph G_2, the vertices 1 and 2 are of degree 1, while vertices 3, 4, and 5 are of the degree 2.

    How can I be sure there aren't more of such graphs? Is there an effective algorithm to find them? Actually, the problem asks to find how many such graphs are there, just the number, and not to specifically draw each one, making the problem presumably easier?

    Many thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    These are called 'unlabled' graph of order 5.
    You found the only two with the degree sequence <1,1,2,2,2>.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    46
    Awards
    1
    Quote Originally Posted by Plato View Post
    These are called 'unlabled' graph of order 5.
    You found the only two with the degree sequence <1,1,2,2,2>.
    Thanks a lot!

    But now I wonder, how can I be sure that I have really found all of the graphs with the degree sequence <1,1,2,2,2> (up to an isomorphism) and that the "search" has been exhaustive?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Do you know about graph cards?
    You may find a website for them, I know of none.
    Anyway I found them in GRAPHS by Wilson & Watkins.
    The two graphs you found are the only to listed on the cards.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 19th 2011, 02:29 AM
  2. Graph Theory Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 18th 2010, 08:36 PM
  3. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 20th 2009, 07:50 PM
  4. graph theory problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 25th 2009, 07:07 AM
  5. Graph Theory problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 9th 2009, 12:50 PM

Search Tags


/mathhelpforum @mathhelpforum