Gráfico sin triángulos con 5 vértices

Question

¿Cuál es la cantidad máxima de aristas en un gráfico sin triángulos en 5 vértices?

Sin respuestas, por favor ... solo consejos.

Creo que E$\leq$ 5, pero no estoy seguro de a dónde ir desde allí.

Answer 1

Considere la posibilidad de un pentágono. Si intenta agregar más los bordes al pentágono un triángulo que se formó. Así de gráfico de tener un ciclo que contiene 5 vértices ( todos los vértices que es ) puede tener como máximo 5 bordes sin violar la condición. Ahora considere la posibilidad de bi-partita gráficos con un total de 5 vértices , decir $x$ en un grupo y $5-x$ en otros. Bipartito gráficos no tiene ciclos de longitud impar. Por lo tanto no hay triángulos y no pentágonos. Como ya hemos tomado el cuidado de los pentágonos. Usted sólo tiene que encontrar el máximo en el caso de bi-partita gráfico. En bi-partita gráfico máxima de los bordes puede ser $(5-x)*x$. La esperanza no he contestado completamente.

Answer 2

Sugerencia: un gráfico libre de triángulos en vértices$5$ es bipartito a menos que contenga un ciclo$5$. Pero si tiene un ciclo de$5$ y está libre de triángulos, es un ciclo.

Por lo tanto, desea encontrar el gráfico bipartito con cinco vértices con la mayoría de los bordes.

Answer 3

No es cierto que esto sea$5$. Conecte un punto a tres puntos, y conecte el punto restante a los mismos tres puntos.

Para probar esto, puede comenzar a distinguir los casos por el grado máximo de un vértice. Puede haber un argumento más elegante, pero no lo sabría por un momento.

Answer 4

Vamos por el bipartito gráfico sugerencia, usted también puede mirar los autovalores de la matriz de adyacencia. Tenga en cuenta que $tr(A) = \sum_{i} \lambda_{i}$ donde $A$ es la matriz de adyacencia y $\lambda_{i}$ son los autovalores. Nota: $tr(A)$ es la traza de $A$, que es la suma de la diagonal de entradas.

Así: $\sum_{i=1}^{5} \lambda_{i} = 0$.

También tenemos:
$\sum_{i=1}^{5} \lambda_{i}^{2} = tr(A^{2}) = 2E$ (El Apretón De Manos Lema)
$\sum_{i=1}^{5} \lambda_{i}^{3} = tr(A^{3}) = 6C_{3}$

Así que si llegamos a la plaza de la matriz de adyacencia, los elementos de la diagonal son las aristas incidentes a cada vértice. Y cubicación de la matriz de adyacencia nos deja con los elementos de la diagonal de conteo de triángulos de cada vértice es una parte de. Dividimos por $S_{3}$ a cuenta por el orden de los vértices del triángulo en un pie.

Ahora también tenemos otro hecho: $\lambda_{i} = -\lambda_{n-i}$ fib $G$ es bipartito. Por lo $\lambda_{1} = -\lambda_{5}$$\lambda_{2} = -\lambda_{4}$. Que nos da la $\lambda_{3} = 0$.

Y así: $2\lambda_{1}^{2} + 2\lambda_{2}^{2} = 2E \implies \lambda_{1}^{2} + \lambda_{2}^{2} = E$.

Y un último dato: $d_{avg}(G) \leq \lambda_{1} \leq \Delta(G)$. Es decir, $\lambda_{1}$ entre el promedio de grado de la gráfica y el mayor grado de los vértices.

Podría ser divertido para jugar con los autovalores aquí para ver lo que pueda venir.