Pregunta de teoría de grafos sobre el grado promedio

Question

El grado promedio de $G = (V, E)$$\frac{\sum_{v\in V}d(v)}{|V|}$. Deje $G = (V, E)$ ser un el gráfico de grado medio $d$ y sin vértices aislados.

Debe haber un vértice $v ∈ V$, de modo que el grado promedio de los vecinos de $v$ es en la mayoría de las $d$?

Sé que este es un problema clásico de la teoría de grafos, pero me parece que no puede resolver. Yo ya demostró que si se sustituye "a la mayoría" con "al menos", entonces la respuesta es "Sí". También sé, que la respuesta a esta pregunta debe ser "No".

Si tales vértice no existe, $\forall v \in V$ tenemos que $$\sum_{w \in \Gamma(v)}d(w)>d\cdot d(v)$$

Resumiendo todas estas desigualdades da

$$|V|\sum_{v \in V}d^2(v)>(\sum_{v \in V}d(v))^2$$

Por lo tanto, por Cauchy-Schwarz no necesitamos todas las titulaciones a ser igual, pero no creo que esto ayuda

También he tratado de construir contraejemplos el uso de algún tipo de simetría mediante el aislamiento de las $2$ vértices y tratando de unirse a todos los demás a ellos, pero fue en vano.

Cualquier sugerencia se agradece!

Answer 1

Si la respuesta es no, entonces un solo contraejemplo es suficiente.

Aquí está una gráfica (fuente):

Aquí, hay tres vértices de grado $1$ y tres vértices de grado $3$; el grado medio es el $2$. Para los vértices en el medio, el grado promedio de sus vecinos,$\frac{1+3+3}{3} = \frac73 > 2$, y para los vértices en el exterior, el grado promedio de sus vecinos,$3$.