# TDA ex-Algoritmos-3 | 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? ## Proposición $P(n)$: Si $G$ es un grafo, con $|V(G)| = 2n$, y $|E(G)| > n^2$, entonces $G$ contiene al menos un triángulo. ## Caso base Veamos que vale $P(1)$. Queremos probar que si $G$ es un grafo con $|V(G)| = 2$, y $|E(G)| > 1^2$, entonces $G$ contiene un triángulo. Sabemos que para todo grafo $G$, $|E(G)| \le \frac{|V(G)| (|V(G)| - 1)}{2}$, porque a lo sumo tiene todas las aristas que puede tener, una entre cada par de vértices distintos. Luego, $G$ tiene a lo sumo $\frac{2 * 1}{2} = 1$ arista, y luego nunca puede pasar que $|E(G)| > 1$. Luego, vale la implicación de $P$, porque el antecedente es trivialmente falso. ## Paso inductivo Sea $n \in \mathbb{N}, n > 1$. Veamos que vale $(P(n) \Rightarrow P(n+1))$. Es decir, queremos probar $P(n+1)$, y podemos asumir $P(n)$. Para probar $P(n+1)$, sea $G$ un grafo con $|V(G)| = 2(n+1)$, y $|E(G)| > (n+1)^2$. Queremos ver que $G$ contiene un triángulo. Como $|E(G)| > (n+1)^2 \ge 1$, existe alguna arista $\{v, w\} \in E(G)$. Consideremos $G' = (G - v) - w$. Notar que $G'$ tiene $2n$ vértices. Si $|E(G')| > n^2$, entonces por hipótesis inductiva $G'$ contiene un triángulo, y luego $G$ contiene un triángulo, que es lo que queríamos demostrar. Si $|E(G')| \le n^2$, como sabemos que $|E(G)| > (n+1)^2$, tenemos que $|E(G)| - |E(G)'| > (n+1)^2 - n^2 = n^2 + 2n + 1 - n^2 = 2n + 1$. Luego, $|E(G)| - |E(G')| \ge 2n + 2$. Calculemos cuántas aristas tiene $G'$. $|E(G')| = |E(G)| - d(v) - d(w) + 1$. Esto es porque le sacamos todas las aristas incidentes a $v$, todas las aristas incidentes a $w$, pero si restamos ambos, estamos contando dos veces la arista $\{v, w\}$, luego sumamos 1 para no contar dos veces esa arista. Juntando esto con la desigualdad de arriba, tenemos que $|E(G)| - |E(G')| = d(v) + d(w) - 1 \ge 2n + 2$, y luego $d(v) + d(w) - 2 \ge 2n + 1$. Vemos que $d(v) + d(w) - 2$ es el tamaño del conjunto de aristas en $G$ que salen de $v$ o $w$, y llegan a alguien en $G$ que no es ni $v$ ni $w$ (restamos 2 porque $\{v, w\}$ está contado en ambos $d(v)$ y $d(w)$, y no lo queremos contar ninguna vez). Es decir, que llegan a alguien en $V(G) \setminus \{v, w\} = V(G')$. Como sólo hay $|V(G')| = 2n$ de esos otros vértices, pero al menos $2n + 1$ aristas en $G$ que salen de $v$ o $w$ y que llegan a $V(G')$, existen dos aristas en $G$ que salen de $v$ o $w$ y van al mismo vértice $z$ en $G'$. Como $G$ es un grafo, y no multigrafo, esas aristas no pueden venir del mismo vértice (es decir, ambas viniendo de $v$ o ambas viniendo de $w$). Luego, existe un vértice $z$ en $G'$, tal que $v$ tiene una arista con $z$, y $w$ tiene una arista con $z$. Esto forma un triángulo en $G$, $\{v, z\}, \{z, w\}, \{w, v\}$, que es lo que queríamos demostrar. ## Extensión Sí, existe tal $c: \mathbb{N} \to \mathbb{N}$. En particular, vale el siguiente teorema: * Teorema (Mantel, 1907). Cualquier grafo $G$ con $n$ vértices y más de $\left \lfloor \frac{n^2}{4} \right\rfloor$ aristas contiene al menos un triángulo. Y luego $c(n) = \left \lfloor \frac{n^2}{4} \right\rfloor$, y $n_0 = 1$. Ahora demostremos este hecho, por inducción. * $P(n)$ = Si $G$ es un grafo con $n$ vértices y $m$ aristas, y $m > \left \lfloor \frac{n^2}{4} \right\rfloor$, entonces $G$ contiene al menos un triángulo. Vemos que $P(1)$ es trivialmente cierto, porque no hay un grafo con $1$ vértice pero $m > \left\lfloor \frac{1^2}{4} \right\rfloor = 1$ aristas, dado que hay un único tal grafo, y tiene $m = 0$ aristas. $P(2)$ vale similarmente, todo grafo de $n = 2$ vértices tiene a lo sumo $m = 1$ arista, luego nunca puede pasar que $m > \left\lfloor\frac{2^2}{4}\right\rfloor = 1$, y la proposición es cierta. Ahora sea $n > 2$, y probemos $P(n)$. Sea $G$ un grafo con $n$ vértices y $m$ aristas. En vez de probar que "Si $m > \left\lfloor\frac{n^2}{4}\right\rfloor$, entonces $G$ tiene un triángulo", voy a probar "Si $G$ no tiene un triángulo, entonces $m \le \left\lfloor\frac{n^2}{4}\right\rfloor$", que es el contrarecíproco, y luego lógicamente equivalente. Asumo, luego, que $G$ no tiene triángulos. Si $m = 0$, terminé, porque $0 \le \left\lfloor\frac{n^2}{4}\right\rfloor$. De lo contrario, $m > 0$, y existe alguna arista $\{x, y\}$ en $G$. Consideremos $G' = (G - x) - y$. Como $G'$ tiene $n - 2$ vértices, y (obviamente) no tiene triángulos (porque $G$ no los tiene), entonces podemos usar la hipótesis inductiva para ver que $G'$ contiene a lo sumo $\left\lfloor \frac{(n-2)^2}{4} \right\rfloor$ aristas. Consideremos todas las aristas que sacamos a $G$ cuando le sacamos a $x$ e $y$, excluyendo a $\{x, y\}$ misma. Hay $|V(G')| = n - 2$ vértices a donde pueden ir estas aristas, y todas salen de $x$ o de $y$. Si hubiera entonces al menos $(n - 2) + 1 = n - 1$ tales aristas, entonces por el principio del palomar tendríamos un triángulo en $G$, puesto que tendríamos dos aristas yendo al mismo vértice $z$ en $G'$, y que salen de $x$ o $y$. Como no pueden salir ambas de $x$ o ambas de $y$ por ser $G$ grafo y no multigrafo, entonces existen las aristas $\{x, z\}$ y $\{z, y\}$, que junto con $\{x, y\}$ generan un triángulo en $G$. Sabíamos que eso no puede pasar, porque asumimos que $G$ no tiene triángulos. Luego, hay a lo sumo $n-2$ tales aristas, que junto con $\{x, y\}$ y $E(G')$ forman todas las aristas en $E(G)$. Esto implica que $|E(G)| \le (n - 2) + 1 + |E(G')| = n - 1 + |E(G')|$. Usando la hipótesis inductiva en $G'$, obtenemos que $|E(G)| \le n - 1 + \left\lfloor\frac{(n-2)^2}{4}\right\rfloor = \frac{4n-4}{4} + \left\lfloor\frac{n^2 - 4n + 4}{4}\right\rfloor = \left\lfloor\frac{4n - 4 + n^2 - 4n + 4}{4}\right\rfloor = \left\lfloor \frac{n^2}{4} \right\rfloor$, que es lo que queríamos demostrar.