Es un gráfico de grado mínimo $\delta$ , $\delta$ -¿conectado por el borde?

Question

Sea G una $\lambda$ -grafo conectado por aristas con $n$ vértices y grado mínimo $\delta$ . Demostrar que si $\delta \ge n/2$ entonces $\delta=\lambda$ .

Lo que pensé fue utilizar el teorema de Whitney: si para cada par de vértices (u,v) hay al menos k caminos independientes entre u y v, entonces el grafo está conectado por k aristas.

Digamos que en nuestro grafo elegimos 2 vértices distintos $u,v$ . Entonces debe ser $N(u) \cap N(v) \neq \emptyset$
(porque si $N(u) \cap N(v) = \emptyset$ entonces $|N(U) \cup N(v)|=|N(u)|+|N(v)|=n$ pero u,v no se tuvieron en cuenta). Entonces debe haber exactamente 2 nodos que estén conectados a u y v.
El único caso en que esto no es cierto es si $v\in N(u)$ o viceversa.

A partir de aquí estaba pensando en ver si puedo encontrar los n/2 caminos entre pares de vértices basándome en la descripción aproximada de cómo debe ser el grafo, pero parece difícil hacerlo. ¿Estoy en el buen camino o tengo que utilizar otro método?

Answer 1

Este sería mi enfoque:

Sea $G=(V,E)$ . Es evidente que $\lambda \leq \delta$ porque eliminar las aristas incidentes en algún vértice $v$ de grado mínimo desconectará $G$ . Así que la pregunta es ¿por qué no estrictamente menos? El comienzo es bastante sencillo:

Supongamos que $\lambda < \delta$ . Conectividad de borde $\lambda$ simplemente significa que tenemos una partición $V=A\,\dot\cup\, B$ con exactamente $\lambda$ bordes entre $A$ y $B$ . Digamos $A$ es la clase de partición más pequeña (no más grande), por lo que $|A|\leq|B|\Rightarrow |A|\leq n/2$ . Cada $v\in A$ puede tener como máximo $|A|-1$ vecinos en $A$ por lo que debe tener al menos $\delta-|A|+1\geq 1$ vecinos en $|B|$ . Esto hace que al menos $|A|\cdot(\delta-|A|+1)\geq|A|$ bordes de $A$ a $B$ (por lo tanto, tenga en cuenta $\lambda\geq |A|$ ). Veremos que son demasiados . En primer lugar, concluye

$$(*)\qquad\lambda \geq |A|\cdot(\delta-|A|+1)>|A|\cdot(\lambda-|A|+1). $$

Si $|A|=1$ tenemos $\delta=\lambda$ . Por lo tanto, supongamos $|A|> 1$ . Algunos jugando con $(*)$ le dará $\lambda <|A|$ . Esto contradice $\lambda\geq |A|$ . $\square$