have the following problem in graph theory.
Let G be a graph with average degree d.
(a) Show that there is a vertex u in V(G) so that the average degree of neighbours of u is at least d.
(b) Must there be a vertex u in V(G) so that the average degree of neighbours of u is at most d ?
I've found some hints. Could anyone help me to use them?
For (a) : compute the average of the degrees of the neighbours of u using that
x/y+y/x>=2 for x,y>0
For (b): Construct an infinite family of connected graphs. A regular graph can't work. Vertices of high and low degrees are needed but both must be adjacent to high degree vertices.
Any idea?


LinkBack URL
About LinkBacks