Mayor valor propio de la matriz de adyacencia de un grafo

Question

Sea $G$ sea un grafo conexo con $n$ vértices y $m$ bordes. Supongamos que $\lambda_1$ es el mayor valor propio de la matriz de adyacencia de $G$ . Sé que $\lambda_1\geq 2m/n$ con igualdad si y sólo si $G$ es un grafo regular, pero no puedo demostrarlo. ¿Podría ayudarme a demostrarlo?

Answer 1

SUGERENCIA:

Sea $A$ sea la matriz de adyacencia del grafo, $\lambda_1$ su mayor valor propio. Entonces $\lambda_1 I - A$ es semidefinida positiva. Ahora la suma de las entradas de una matriz semidefinida positiva es $\ge 0$ . Concluimos que $$n \lambda_1 - 2 m \ge 0$$

Obsérvese que la suma de las entradas de $\lambda_1 I - A$ es igual a $$\langle (\lambda_1 I - A) v , v\rangle$$ donde $v = (1,\ldots, 1)$ . Si tenemos igualdad, $v$ debe estar en el núcleo de $\lambda_1 I - A$ .