# TDA | Practica 3 Ejercicio 9 ## Consigna - Demostrar por inducción que todo grafo tiene $2n$ vértices con más de $n^2$ aristas tiene algún triangulo. **¿Se puede dar una cota mejor que funcione a partir de algún $n_0$?** Es decir, ¿Existe $c(n) < n^2$ tal que todo grafo de $n \geq n_0$ vertices con más de $c(n)$ aristas tenga triangulos? ## Resolución - A mí me están diciendo que: - $\forall \ G$ tal que $|E(G)|>n^2 \Rightarrow$ "Tiene algún triangulo". - $\exists c(n)<n^2 / \ \forall G \ n \geq n_0$ vertices > $c(n)$. - Caso base: $n=2$ - Asumimos un grafo con $4$ vértices y más de $4$ aristas. - Es sencillo verificar que tal grafo debe contener un triángulo, dada la densidad de conexiones. -  - Paso inductivo: sea $|E(G)|>n^2$ con $2n=|V(G)|$ **verdadero**, o sea que asumo que esto vale y se cumple. - Hipótesis Inductiva (HI): - Suponemos que para un entero $n$, cualquier grafo $G$ con $2n$ vértices y más de $n^2$ aristas contiene al menos un triángulo. - Queremos demostrar que para $n+1$, cualquier grafo $G$ con $2(n+1)$ vértices y más de $(n+1)^2$ aristas también contiene al menos un triángulo. - Quiero ver Que: $|E(G)|>(n+1)^2$ con $2(n+1)=|V(G)| \Rightarrow \exists$triangulo # - Tomo $v_1,v_2$ que están conectados. - Tenemos dos casos: - Caso 1: $v_1$ y $v_2$ forman un triangulo - Caso 2: $v_1$ y $v_2$ no forman un triangulo - ~~TBD a desarrollar esto~~ - **No está bien, hay que corregir** - $V(G-${$v1, v2$}$)$ tiene $2n$ vértices, Ahora quiero ver qué **también cumple** $E(G-${$v1, v2$}$) > n^2$ para poder usar la HI. - Análisis de aristas en $G-${$v_1,v_2$}: - $$|E(G - \{v_1,v_2\})| = |E(G)| - (d(v_1)+d(v_2)-1)$$ - Podemos acotar $d(v_1) + d(v_2)$ por $2(n+1) - 1$, ya que cada vértice puede estar conectado a todos los demás exceptoa así mismo y al otro vértice en cuestión. - Demuestro que $E(G-${$v_1, v_2$}$) > n^2:$ - Como hipótesis tengo que $G$ cumple: $|E(G)| > (n+1)^2$ - Sacándole $v_1$ y $v_2$: - $$|E(G-[v_1, v_2])| = |E(G)| - (d(v_1) + d(v_2) - 1) \geq |E(G)| - ( (2(n+1)-1) - 1) = |E(G)| - 2n$$ - $\rightarrow ~$Puedo acotar usando que $d(v1) + d(v2) \leq 2*(n+1)-1 = 2*n + 1$ porque $v_1$ y $v_2$ no pueden compartir vecinos. Luego, como estoy restando algo más grande, el resultado es más pequeño. - $= |E(G)| - 2n > (n+1)^2 - 2n$ - $\uparrow \uparrow \uparrow$ Acá usé que $|E(G)| > (n+1)^2$ - $= n^2 + 1 = n^2 +1 > n^2$ - Es decir, $|E(G-${$v_1, v_2$}$)|$ $> n^2 \Rightarrow$ puedo aplicar la HI $\Rightarrow G-${$v_1, v_2$} tiene triángulo! - Finalmente como $G-${$v_1, v_2$} es subgrafo de $G$: - >Si G-{v_1, v_2} tiene triángulo, G también lo tiene - (Los vértices y aristas del triángulo de $G-${$v_1, v_2$} son parte del grafo original, por lo cual el triángulo también está en G. El hecho de añadir v1 y v2 junto a todas sus aristas no tiene porqué cambiar esto). $\square$ ```text Idea: Acotar que v_1 a lo sumo comparte una arista con todos los otros vertices de G, y como hay 2(n+1) vertices en G, luego hay 2(n+1)-3 aristas incidentes a v_1, a lo sumo todas menos v_1 mismo y luego d(v_1) <= 2(n+1)-1. Por el mismo argumento d(v_2) <= 2(n+1)-1. Luego: Para acotar la suma podemos decir que d(v_1) + d(v_2) <= 2(n+1) - 1 + 2(n+1) - 1 = 4(n+1) - 2 Se escribe "Sea G un grafo, con |V(G)| = 2n, y |E(G)| > n^2." ```