Results 1 to 5 of 5

Math Help - 8,7,7,7,7,3,3,3,3,2 a Possible Graph?

  1. #1
    Newbie emterics90's Avatar
    Joined
    Jan 2006
    Posts
    12

    8,7,7,7,7,3,3,3,3,2 a Possible Graph?

    Q: Can a graph of order 10 have one vertex of degree 8, four vertices of degree 7, four of degree 3, and one of degree 2?

    That is, can the graph 8,7,7,7,7,3,3,3,3,2 exist?

    I am told the answer is no. However, for multigraphs yes this is possible. I don't know why. I have tried using the Handshake Theorem, but that doesn't tell me much.

    Does anybody know which theorem proves that the graph above cannot exist unless it is a multigraph? What is the reason why it cannot exist?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Mar 2008
    Posts
    12
    No, it's not a possible graph. We can prove this fact by using the following theorem:

    Theorem: If the sequence r,s_1,s_2,...,s_r,t_1,t_2,...,t_k is a degree sequence of graph with r+k+1 vertices, then the sequence s_1 - 1,s_2 - 1,...,s_r -1,t_1,t_2,...,t_k (rearranged in a decreasing way) is a degree sequence of a graph with r+k vertices.

    Step 1.a: 8|7,7,7,7,3,3,3,3|2
    Step 1.b: 6,6,6,6,2,2,2,2,2
    Step 1.c: 6,6,6,6,2,2,2,2,2(rearranged but remained same)

    Step 2.a: 6|6,6,6,2,2,2|2,2
    Step 2.b: 5,5,5,1,1,1,2,2
    Step 2.c: 5,5,5,2,2,1,1

    Step 3.a: 5|5,5,2,2,1|1
    Step 3.b: 4,4,1,1,1,1
    Step 3.c: 4,4,1,1,1,1

    Now without going any further, one can show that this cannot be a degree sequence of a simple graph.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2006
    Posts
    77
    Not sure if this is correct but nothing sticks out to me:

    The complete graph K_{n} has at most \frac {1}{2}n(n+1) edges. For n = 10, this gives 55.

    Your graph has 50 edges and 10 vertices, so you need to remove 5 edges from K_{10}. Note that K_{10} has all vertices with degree 9, so removing 5 can never leave one vertex with a degree of 2. Therefore the stated graph cannot exist.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2008
    Posts
    12
    For this question, your method is definitely much more efficient than the algorithm i gave. But in general, we encounter with more complicated situations and it's better to use the degree-sequence algorithm.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by Thomas154321 View Post
    Not sure if this is correct Your graph has 50 edges and 10 vertices
    There is a problem with that solution.
    The degree sum is twice the number of edges.
    Therefore, the number of edges is 25 not 50.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 02:30 PM
  3. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  4. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM
  5. Replies: 1
    Last Post: February 15th 2009, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum