# TDA | Practica 3 Ejercicio 4a ## Consigna - a) *Demostrar, usando inducción en la cantidad de vértices, que todo grafo de $n$ vértices que tiene más de $\frac{(n-1)(n-2)}{2}$ aristas es conexo. Opcionalmente, puede demostrar la misma propiedad usando otras técnicas de demostración. ## Resolución ### Para tener en cuenta antes de empezar a leer: #### Definiciones por partición de casos: - ~$d(v)$: Este símbolo representa el grado del vértice $v$, es decir, el número de aristas que conectan $v$ con otros vértices en el grafo. En el contexto de nuestro análisis, examinamos casos basados en el grado de un vértice particular $v$. - Partición de casos: - donde $d(v) > 0$: consideramos un vértice $v$ que está conectado por al menos una arista. Este caso es crucial porque, al remover $v$ del grafo, todavía tenemos un número suficiente de aristas que garantizan, según nuestra hipótesis inductiva, que el subgrafo resultante $G-v$ es conexo. - donde $d(v) \leq k-1$: Incluso después de remover $v$ y sus aristas asociadas, el número de aristas restantes en $G-v$ es suficiente para mantener la conectividad del subgrafo. Esto se deduce al realizar el cálculo $\frac{k(k-1)}{2} - (k-1)$, que simplifica a $\frac{(k-1)(k-2)}{2}$, garantizando que el subgrafo de $k$ vértices sigue siendo conexo según nuestra hipótesis inductiva. ### Demostración # - Sea caso base $K = 1$ un vertice sin aristas, no se estaría cumpliendo - Sea caso base $K = 2$ dos vertices con una arista, acá ya sí se estaría cumpliendo pues $\frac{(2-2)(2-1)}{2} = 0 \ \Rightarrow |E| > 0$. - Entonces como no existe grafo de 1 vértice que cumple el antecedente, para todos los grafos de 1 vértice se cumple. - Supongamos que lo probamos hasta $K$, o sea que asumimos que nuestra proposición vale hasta para $K$, tomandolo como hipotesis inductiva. - $P(k):$ Grafo con n vertices y $|E| > \frac{(k-1)(k-2)}{2} \Rightarrow G$ conexo. - $P(k+1) =^?$ "Grafo con $k+1$ vertices y con $|E| > \frac{k(k-1)}{2}$" # - V : ~$d(v)=$ k $\Rightarrow \ G$ es conexo - ~$d(v) \leq k-1$ - Elijo un $v$ con $d(v) > 0$ porque si no existiera entonces $|E|=0$ - Pero además por hipotesis, $|E|>\frac{k(k-1)}{2} \ \iff |E| > 0 \ (k\geq2)$ - $\Rightarrow$ $|E| > 0$ y $|E| = \ 0$ **Contradicción!** - Ahora ~$d(v)\leq k-1 \ :$ - $|E(G-v)|$ = $E(g) - d(v) \ \iff$ - $> \ \frac{k(k-1)}{2}-d(v)$ - $\geq \ \frac{k(k-1)}{2} - (k-1)$ - $= (k-1)(\frac{k}{2}-1)$ - $\frac{(k-1)(k-2)}{2}$ - Ahora tomo $G' = G-v$ - $|E(G')| = |E(G-v)| > \frac{(k-1)(k-2))}{2}$ - $|V(G')| = k$ - $\Rightarrow G'$ Conexo. - $G = G' \cup v$ - $E = E(G-v) +$ "Aristas que sacamos de g al remover v" - $w_1, w_2 \in G$ si $w_1, w_2 \in G'$ Hay un camino en $G'$ que los une y por lo tanto en G. - $w_1 \in G', v$ $d(v)>0 \ \exists \ w_2 \in G' / (w_2,v)$ - Dibujo de la idea: -  - Agarro el camino en $G'$ entre $w_1 \ \land \ w_2$ y luego el arco $(w_2,v) \ \square$