$ x_{k+1} \in \{ 2x_k, 2x_k-1, 2x_k-2014, 2x_k-2015 \}$.
2. Se tiene una gráfica de $n$ vértices tal que no existen cuatro vértices que todos se conocen entre sí (no hay $K_4$'s). Encontrar el máximo número posible de triángulos ($K_3$'s) que puede tener dicha gráfica.
3. (**) Para un natural $n$, sea $f(n)$ el mayor número posible de aristas que una gráfica de $n$ vértices puede tener si no tiene cuadrados. Probar que existen infinitos enteros $n$ tales que
$f(n) \ge \frac{n^{3/2}}{2}-n$.
(Un cuadrado es un conjunto de 4 vértices distintos $A,B,C,D$ tal que $AB, BC, CD$ y $DA$ son aristas).
1 comentario:
Publicar un comentario