Gráfico con 10 nodos y 26 de bordes deben tener al menos 5 triángulos

Question

Esta no es una tarea pregunta, pero le agradecería si la gente se tratan como si se tratara de la tarea. Estoy buscando (nonspoiler) consejos.

Me gustaría demostrar que, dado cualquier gráfico con 10 nodos y 26 de bordes, debe haber al menos 5 triángulos. Aquí es el progreso que he hecho hasta ahora:

1. Sé que un gráfico con $n$ nodos y $\lfloor \frac{n^2}{4} \rfloor + 1$ bordes deben tener un triángulo. También estoy familiarizado con la prueba.
2. Me las arreglé para encontrar un apretado caso de la instrucción donde el número de triángulos es exactamente 5. Esta es la $K_{5, 5}$ gráfico con una ventaja extra.
3. También sé (y creo que puedo demostrarlo) que ningún gráfico con 10 nodos y 25 bordes pero no triángulos debe ser isomorfo a $K_{5, 5}$.
4. Una defectuosa de la prueba sería decir que empezamos añadiendo el 25 bordes asegurándose de que no hay triángulos, entonces la adición de cualquier ventaja extra tendrá como resultado inmediato en 5 triángulos. No hay garantía, sin embargo, que el número mínimo de triángulos se obtiene de esta manera.

Las sugerencias se agradece.

Answer 1

En realidad, es cierto que cualquier gráfico en $2n+\delta$ nodos(donde $\delta$ $0$ o $1$) con exactamente $n(n + \delta) + 1$ bordes tiene al menos $n$ triángulos.

Si recuerdo correctamente, esto puede ser demostrado por inducción en $n$, mostrando que hay un vértice de grado $\leq n$ y, a continuación, eliminar a tratar y aplicar la hipótesis de inducción.