Let $\displaystyle G$ be a graph with average degree $\displaystyle d$. Show that there exists a vertex $\displaystyle v \in V(G)$ such that the average degree of neighbours of $\displaystyle v$ is at least $\displaystyle d$.

Printable View

- Oct 14th 2010, 09:14 AMNewtonianGraph Theory Puzzle
Let $\displaystyle G$ be a graph with average degree $\displaystyle d$. Show that there exists a vertex $\displaystyle v \in V(G)$ such that the average degree of neighbours of $\displaystyle v$ is at least $\displaystyle d$.

- Oct 19th 2010, 01: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...