Condiciones necesarias y suficientes para la simplicidad y conectividad de los grafos

Question

A conectado es un grafo sin subgrafos disjuntos. A simple es un gráfico sin bucles ni aristas múltiples.

Pregunta fácil: ¿Cuáles son las condiciones necesarias y suficientes sobre el orden (número de vértices) y el tamaño (número de aristas) de un grafo dado para garantizar que sea simple y conectado?

Por ejemplo, el único gráfico simple y conexo de orden $2$ y el tamaño $1$ es el gráfico de trayectorias $P_2$ (un segmento de línea). No existe un gráfico simple y conectado de orden $2$ y tamaño mayor o igual a $2$ . Un gráfico con orden y tamaño $3$ es el gráfico del ciclo de orden $3$ (un triángulo). No existe un gráfico simple y conectado de orden $3$ y tamaño mayor o igual a $4$ . Continuando de esta manera, concluyo que debe haber una condición en la diferencia entre el tamaño y el orden (en comparación con el tamaño).

Una pregunta más difícil: Para cualquier par de enteros positivos $(a,b)$ ¿existe un gráfico simple y conectado $G_{ab} = (V_{ab}, E_{ab})$ con el pedido $|V_{ab}| = \frac{1}{2}(ab + a + b + \text{gcd}(a,b))$ y el tamaño $|E_{ab}| = ab$ ? Si es así, ¿son significativos estos gráficos?

Por ejemplo, si $b = 1$ entonces $|V_{ab}| = a + 1$ , $|E_{ab}| = a$ y $G_{ab}$ se puede realizar como el gráfico de trayectorias $P_{a+1}$ (o cualquier árbol con el mismo orden), que es a la vez simple y conectado.

Answer 1

Pregunta fácil:

Supongamos que $|V|=n$ . Entonces el gráfico no puede ser simple si $|E|>\binom{n}{2}$ ya que el gráfico completo en $n$ vértices tiene $\binom{n}{2}$ bordes. El gráfico no puede estar desconectado si es simple y $|E|>\binom{n-1}{2}$ . Esto se debe a que el gráfico completo en $n-1$ vértices tiene $\binom{n-1}{2}$ bordes. (Ver este hilo de MSE para una discusión y una prueba). Nótese que para el requisito de conectividad debemos suponer que el grafo es simple, de lo contrario podríamos poner simplemente todo las aristas entre dos vértices.

Una pregunta más difícil: La respuesta es sí. Demostraremos que este grafo tiene más aristas que el árbol de $|V|$ vértices, y menos aristas que el gráfico completo en $|V|$ vértices. (Esto significa que podemos elegir que sea simple y conectado)

Más que un árbol:

Supongamos que $a\geq b$ , y observe que entonces $b\geq 1$ y si $b\neq 1$ tenemos $a\geq 2$ . También, $\gcd(a,b)\leq b$ para que $$ |V|\leq \frac{1}{2}\left( ab+2b+a\right).$$ De ello se desprende que $$|E|-|V|\geq ab- \frac{1}{2}\left( ab+2b+a\right)$$ $$=\frac{1}{2}\left(ab-2b-a+2\right)-1=\frac{1}{2}(a-2)(b-1)-1\geq -1.$$ En consecuencia, $$|E|-|V|\geq -1$$ por lo que tenemos suficientes aristas para conectar el gráfico, ya que el árbol conectado en $|V|$ vértices tiene $|V|-1$ bordes.

Gráfico menos que completo:

Tampoco tenemos demasiadas aristas ya que $\gcd(a,b)\geq 1$ implica $$\frac{1}{2}\left( ab+b+a+1\right)\leq |V|.$$ Esto significa que $$|E|+b+a+1\leq2|V|,$$ y como $b\geq 1$ , $a\geq1$ tenemos $|E|\leq 2|V|-3$ . Pero como $n^2-5n+6\geq 0$ para los enteros $n\geq 1$ vemos que $\frac{n^2-n}{2}\geq 2n-3$ y por lo tanto $$2n-3\leq\binom{n}{2}$$ para cada número entero positivo $n$ . En consecuencia, $|E|\leq 2|V|-3$ implica que $$|E|\leq \binom{|V|}{2}$$ para que el grafo tenga menos aristas que el grafo completo, y se puede elegir que sea simple.

Espero que eso ayude,