Si $G$ es un $(n,m)$ gráfico tal que $\Delta(G)=n-2$ y dos vértices no adyacentes tienen un vecino común, entonces $m\geq 2n-4.$

Question

Dejemos que $G$ sea un gráfico de orden $n$ y el tamaño $m$ tal que $\Delta(G)=n-2$ y dos vértices no adyacentes tienen un vecino común. Demuestre que $m\geq 2n-4.$

Le ruego que me aconseje sobre mi prueba. Gracias.

Dejemos que $v\in G$ tal que $v$ es adyacente a $ v_1,..., v_{n-2}$ y no adyacente a $u.$

Entonces $\sum_{g\in G} \text{deg}(g) \geq (n-2)+(n-2) = 2n-4.$

Supongamos ahora que $u$ es adyacente a $v_1,...,v_k$ y no adyacente a $v_{k+1},..., v_{n-2}.$ Entonces $\sum_{g\in G} \text{deg}(g)$ aumentará en al menos $k+k=2k.$

Dado $v_i(i=k+1,..., n-2), $ por suposición en el problema, existe $v_j(j = 1,..., k)$ tal que $v_j$ es adyacente a $v_i.$ Podemos suponer $v_1$ será adyacente a todos los $v_i(i=k+1,...,n-2).$

Entonces $\sum_{g\in G} \text{deg}(g)$ aumentará en al menos $n-2-k + n-2-k = 2n-4-2k.$

Por lo tanto, $2m = \sum_{g\in G} \text{deg}(g)\geq 2n-4-2k+2k+2n -4 = 4n -8.$

Answer 1

Adoptemos un enfoque constructivo. Se nos da lo siguiente:

(1) $G$ tiene $n$ vértices

(2) $G$ tiene $m$ bordes

(3) $\Delta(G)=n-2$ es decir, el grado máximo de cualquier vértice en $V(G)=n-2$

(4) Dos vértices no adyacentes comparten un vecino. Es decir, si $u,v\in V(G)$ tal que $u\nleftrightarrow v$ entonces existe algún $w\in V(G)$ tal que $u\leftrightarrow w$ y $v\leftrightarrow w$ .

Dejemos que $v\in V(G)$ tal que $\delta(v)=n-2$ . Nombra los vértices adyacentes $v_i$ tal que $i\in\{1,\dots,n-2\}$ . En este punto, sabemos $|E(G)|\geq n-2$ . Además, nuestra elección de $v$ implica que debe existir $u\in V(G)$ tal que $v\nleftrightarrow u$ . Sin embargo, la propiedad (4) implica que $u\leftrightarrow v_j$ para algunos $j\in\{1,\dots,n-2\}$ . Por lo tanto, $|E(G)|\geq n-1$ .

Todavía tenemos que considerar si $u$ es adyacente a cualquiera de los otros vértices $v_\ell$ , donde $v_\ell\in\{1,\dots,j-1,j+1,\dots,n-2\}$ . Observe que hay $n-3$ elementos de este conjunto. No sabemos con seguridad cuántos de estos vértices son adyacentes a $u$ Así que vamos a suponer que $u$ es adyacente a $k$ de estos vértices donde $0\leq k\leq n-3$ . Así, $|E(G)|\geq n-1+k$ .

Queda $(n-3-k)$ vértices en el conjunto $\{1,\dots,j-1,j+1,\dots,n-2\}$ que son no junto a $u$ . Una vez más, la propiedad $(4)$ implica que cada uno de estos vértices debe ser entonces adyacente a algún vértice que es junto a $u$ . Así que debe ser el caso que $$|E(G)|\geq (n-1+k)+(n-3-k)=2n-4$$ o de forma equivalente $m\geq 2n-4$ .