Results 1 to 2 of 2

Math Help - Graph Theory

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Graph Theory

    Let n be a positive integer. Let d be a list of n non-negative integers with even sum,
    where the largest is less than n and di ffers from the smallest entry by at most 1. Prove that d is graphic.

    Any THoughts?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    We will call a sequence that satisfies the properties given in the problem a "good sequence". Arrange the sequence in decreasing order. What remains to show is that it satisfies the Havel-Hakimi sufficient conditions for being a graphic sequence.

    Graphic Sequence -- from Wolfram MathWorld

    Suppose there are p elements of value x and q elements of value x-1 initially. Remove the leftmost element from the sequence, and decrease the next x elements by 1. This is always possible since p<n. If p>x, the number of elements of value x-1 will be x+q, and the number of elements of value x will be p-x-1. If p<=x, the number of elements of value x will be 0, the number of elements with value x-1 will be p-1+n-1-x, and the number of elements of value x-2 will be x-p+1.

    So in both the cases, a good sequence remains good. We again arrange it in decreasing order and repeat the whole process. In this manner, we can reduce it to a sequence of 0s and even number of 1s. Once this is done, it is easy to show that it represents a graph. So by the Havel-Hakimi conditions every good sequence is graphic.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 06:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 26th 2010, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum