Mostrando un límite superior en $\kappa(G)$

Question

Sea $\kappa(G)$ la conectividad de un grafo $G$, $|V| = n$ y $|E|=m$.

Para cualquier grafo $G$, demuestra que si $m \geq n-1$ entonces

$$\kappa(G) \leq \lfloor \frac{2m}{n} \rfloor$$ Lo que sé es que $\kappa(G) \leq \lambda(G) \leq \delta(G)$ donde $\lambda(G)$ es la conectividad de la arista y $\delta(G)$ es el grado mínimo.

¿Podría demostrar que esta es una cota superior en $\delta(G)$?

También sé que por el lema del apretón de manos la suma de los grados de los vértices es el doble del número de aristas; es decir,

$\sum\limits_{v \in V}d(v) = 2|E|$

Cualquier sugerencia o idea sería genial.

Answer 1

Intenta pensar en una interpretación de $\frac{2m}{n}$ y luego relacionarla con el grado mínimo $\delta(G)$.

Pista: La interpretación tiene que ver con el grado.

Nota que $\frac{2m}{n}=\frac{\sum_{v\in V}\deg(v)}{n}$ y puedes pensar en el lado derecho como el grado promedio de los vértices en $G$.