Let be a graph with average degree . Show that there exists a vertex such that the average degree of neighbours of is at least .

Printable View

- October 14th 2010, 10:14 AMNewtonianGraph Theory Puzzle
Let be a graph with average degree . Show that there exists a vertex such that the average degree of neighbours of is at least .

- October 19th 2010, 02:31 PMNewtonian
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...