Para un gráfico$G$, si$m>\binom{n-1}{2}$, entonces$G$ está conectado

Question

Estoy tratando de levantar un poco la teoría de grafos de Bondy y Murty de la Teoría de grafos como se sugiere aquí.

Problema 1.1.12 me ha dado un poco de enganche.

Deje $G$ ser un simple gráfico de la orden de $n$ y el tamaño de la $m$. (Así que hay $n$ vértices y $m$ bordes). Si $m>\binom{n-1}{2}$, $G$ está conectado.

Yo estoy siguiendo una pista en un apéndice que dice que si $G$ no está conectado, se puede partición de los vértices en partes $(X,Y)$ de tal manera que ningún borde une un vértice en $X$ a un vértice en $Y$. ¿Cuál es el mayor número de aristas en $G$ si $|X|=r$$|Y|=n-r$?

Supongo que los gráficos en $X$$Y$, a continuación, completar los gráficos, para un total de $\binom{r}{2}+\binom{n-r}{2}$ bordes. Simplificando, esto es $\frac{2r^2+n^2-2rn-n}{2}$, por lo que estoy tratando de mostrar $$\frac{2r^2+n^2-2rn-n}{2}\leq\frac{(n-1)(n-2)}{2}$$ para obtener el contrapositivo.

La anterior es equivalente, si mi álgebra es correcta, mostrando el $r\geq\frac{n-1}{n-r}$ cualquier $0\lt r\lt n$. Esto parece razonable, pero no puedo demostrarlo. ¿Cómo puedo hacerlo? Gracias.

También me gustaría ser feliz de ver una solución que no necesariamente la de hacer uso de la pista.

Answer 1

$$\begin{align*} r &\ge \frac{n-1}{n-r}\\ rn-r^2 &\ge n-1\\ rn-r^2-n+1 &\ge 0\\ (r-1)n-(r-1)(r+1) &\ge 0\\ (r-1)(n-r-1) &\ge 0 \end{align*}$$