Simple desigualdad del gráfico conectado (diámetro del gráfico)

Question

Demuestre que para un gráfico conectado simple$G$, la desigualdad dada es verdadera: $$ \ operatorname {diam} (G) \ cdot \ delta (G) <3n $$

donde$\operatorname{diam}(G)$ es el diámetro del gráfico$G$,$\delta(G)$ es el grado mínimo del gráfico$G$ y$n$ es el número de todos los vértices en$G$

He estado tratando de resolver estos problemas durante mucho tiempo, y todavía no lo hago. ¿Alguien podría ayudar?

Muchas gracias.

Answer 1

Deje $a_0a_1\ldots a_D$ ser un camino de longitud $D=\operatorname{diam}(G)$ determinar el diámetro de $G$ (es decir, no hay ruta más corta de a$a_0$$a_D$. Para $0\le i\le D$, vamos a $f(i,1),\ldots,f(i,\delta(G))$ ser distintos a los vecinos de $a_i$ (esto es posible mediante la definición de $\delta$). Esto nos da un mapa de $f$ $\{0,\ldots,D\}\times \{1,\ldots,\delta(G)\}$ para el conjunto de $V$ de los vértices de $G$.

Reclamo: Para cada vértice $v$, hay en la mayoría de los tres pares de $(i,j)$$f(i,j)=v$.

Prueba: Supongamos $v:=f(i,j)=f(i',j')=f(i'',j'')=f(i''',j''')$ con cuatro diferentes pares de $(i,j), (i',j'), (i'',j''), (i''',j''')$. A continuación, $i,i',i'',i'''$ son parejas distintas, porque hemos seleccionado distintos a los vecinos en la definición de $f$. Wlog. $i<i'<i''<i'''$, por lo tanto $i'''>i+2$. El camino de $a_0\ldots a_iva_{i'''}\ldots a_D$ se obtiene mediante la sustitución de al menos dos vértices (es decir, al menos $a_{i'}$$a_{i''}$) con un solo vértice, por lo tanto es el más corto de $D$, contradicción. $_\square$

Como consecuencia $$3n\ge (D+1)\cdot \delta(G).$$