El número máximo de aristas en un grafo sin ciclos pares con $n$ vértices

Question

Problema Dado un número entero positivo cualquiera $n$ ¿cuál es el número máximo de aristas en un grafo sin ciclos pares con $n$ ¿Vértices?

¿Es el problema anterior un problema no resuelto en la teoría de grafos extremos? ¿Hay algún resultado sobre este problema?

Answer 1

La respuesta es $\lfloor \frac{3}{2}(n-1)\rfloor$ . Primero hay que tener en cuenta que si $G$ es $2$ -y libre de ciclos pares, entonces $G$ debe ser un ciclo impar. Para ver esto, considere un oreja-descomposición de $G$ . Si $G$ no es sólo un ciclo, entonces $G$ contiene un ciclo y una oreja. Sin embargo, por consideraciones de paridad, un ciclo y una espiga siempre contienen un ciclo par.

Ahora dejemos que $G$ sea un gráfico arbitrario libre de ciclos pares y considere su bloque-árbol cortado $T$ . Por la observación anterior, cada bloque de $G$ es un ciclo impar o sólo una arista. Para maximizar el número de aristas, cada bloque de $G$ debe ser un triángulo. Así, el número máximo de aristas se consigue con un "árbol de $k$ triángulos". Este gráfico tiene $3k$ bordes y $2k+1$ vértices. Para $n$ incluso (digamos $n=2k+2$ ), el máximo se alcanza cuando $T$ tiene exactamente $k$ bloques que son triángulos y exactamente un bloque que es una arista. Esta es una caracterización completa de los ejemplos extremos.