Te sugerimos que pruebes esta respuesta en un ambiente controlado antes de enviarlo a producción, un saludo.
Solución:
Para (2), parece ser más fructífero pensar en lo que máximo número de bordes para un no conectado gráfico es. (El número que estás buscando es entonces uno más).
Si un gráfico no está conectado, sus vértices se dividirán en dos grupos que no se conectan entre sí; digamos, elija un vértice y deje que un grupo consista en todos los vértices conectados a ese, y el otro grupo serán todos los demás vértices. .
Suponga que los grupos tienen un tamaño $ a $ y $ b $, con $ a + b = 40 $. Entonces la máximo el número de aristas que puede tener el gráfico es $ binom a 2 + binom b 2 $, pero una forma más útil de escribir esto es $ binom a + b 2 -ab $, es decir, el gráfico completo menos el número de aristas que conectarían los dos grupos. Como tenemos $ b = 40-a $, necesitamos minimizar la función $ a mapea a a (40-a) $ bajo la restricción de que $ a $ es un número entero entre $ 1 $ y $ 39 $, inclusive.
¿Puedes completarlo desde aquí?
[Edit: for the sake of completeness I added, in the end, the proof for the right answer for 2]
¡Te perdiste la respuesta correcta para 1) por 1! Imagina que ordenas todos tus 40 vértices en una línea y luego conectas cada uno con el siguiente. Entonces tendrías 39 aristas y tu gráfica estaría conectada. Por lo tanto, un gráfico con $ k $ vértices necesita por lo menos $ k-1 $ bordes que se conectarán …
Ahora, para responder a su segunda pregunta … ¿Cuál es el “peor escenario” de tener bordes distribuidos en su gráfico y aún no tener un gráfico conectado? Bueno, imagina que dejas un vértice ahí sin aristas y conecta completamente todos los $ k-1 $ vértices que quedan. ¿Cuántos bordes tiene eso? ¿Es suficiente?
Se puede probar que ese es el máximo número de aristas que puede tener un gráfico con $ k $ vértices y aún no estar conectado. ¿Porqué es eso?
(Si después de pensar un poco en esto no te convences de ese hecho y / o no puedes probarlo, puedo escribir la prueba por ti. Pero tienes que esforzarte lo suficiente).
Prueba:
Sea $ n $ el número de vértices de una gráfica. Demostramos que $ n-1 choose 2 $$ + 1 $ es el número mínimo de aristas que debe tener la gráfica para estar seguros de que la gráfica está conectada. Para eso, primero mostramos que si el gráfico tiene $ n-1 choose 2 $ bordes, entonces no es necesario que esté conectado.
Esa afirmación se cumple trivialmente: elija un vértice y considere los $ n-1 $ vértices que quedan. Podemos conectarlos todos con $ n-1 choose 2 $ bordes. Debido a que había un vértice que se había dejado de lado, ese vértice no tiene bordes incidentes y, por lo tanto, está aislado del resto del graoh, es decir, el gráfico es no conectado.
En segundo lugar, mostramos que no hay forma de distribuir $ n-1 choose 2 $$ + 1 $ aristas entre $ n $ vértices que deja el gráfico desconectado. Suponemos que existe tal distribución. Luego, el gráfico se puede dividir en dos componentes. Uno $ G_1 $ con $ k $ vértices y el otro $ G_2 $, con $ nk $. Sin pérdida de generalidad, suponga $ k le nk $. Para que esos dos componentes tengan tantos bordes como sea posible, deben estar completamente conectados. Eso significa que cada vértice en $ G_1 $ tiene $ k-1 $ aristas y cada vértice en $ G_2 $ tiene $ nk-1 $ aristas.
Ahora que $ G_2 $ tiene más vértices que $ G_1 $, podríamos elegir un vértice de $ G_1 $, borrar todos sus bordes, moverlo a $ G_2 $ y conectarlo a cada vértice allí. Eso sería crear al menos tantos bordes como destruyó, por lo que no está disminuyendo el número total de bordes en nuestro gráfico. Podemos repetir este proceso para aumentarlo. Siempre que queden vértices en $ G_1 $, esto deja el gráfico desconectado. Entonces, el número mínimo de vértices en $ G_1 $ es 1. Pero ese es exactamente el caso anterior, por lo que queda un borde por asignar, y debe conectar el único vértice desde $ G_1 $ a algún vértice en $ G_2 $ haciendo el gráfico conectado.
Al mostrar que para cualquier gráfico desconectado dividido en más de 2 componentes, puede tener un gráfico desconectado con más bordes y solo 2 componentes, mostramos que dividir $ G $ en $ G_1 $ y $ G_2 $ fue nuestra mejor opción, pero en ese caso no podríamos haberlo hecho mejor. Entonces, tener $ n-1 choose 2 $$ + 1 $ bordes es suficiente para garantizar que el gráfico esté conectado.
Nos encantaría que puedieras comunicar esta sección si te fue de ayuda.