Results 1 to 2 of 2

Math Help - Graph Theory Puzzle

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    15

    Graph Theory Puzzle

    Let G be a graph with average degree d. Show that there exists a vertex v \in V(G) such that the average degree of neighbours of v is at least d.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Oct 2010
    Posts
    15
    Does anyone have any ideas? Incidentally, there does not necessarily have to exist a vertex such that the average degree of neighbours is at most d, so I think there is at least something slightly subtle going on...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  2. A number theory puzzle
    Posted in the Math Puzzles Forum
    Replies: 9
    Last Post: September 16th 2010, 09:46 AM
  3. Replies: 0
    Last Post: May 20th 2010, 08:58 AM
  4. Set theory Puzzle
    Posted in the Math Puzzles Forum
    Replies: 4
    Last Post: January 25th 2010, 09:11 AM
  5. puzzle, set theory or statistics or probability
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 21st 2009, 05:24 AM

/mathhelpforum @mathhelpforum