Demuestra que el número máximo de aristas en un grafo sin ciclos pares es floor(3(n-1)/2)

Question

La pregunta está en el título. Puedo ver por qué el límite es agudo (por ejemplo, un montón de triángulos que comparten un vértice común si n es impar, o lo mismo pero con una arista sobrante colgando si n es par). Pero no puedo demostrar por qué el límite es el mejor posible.

Sé que cada arista debe pertenecer como máximo a un ciclo. Estaba pensando que podría tomar cualquier camino o ciclo impar grande y convertirlo en un montón de triángulos siempre que sea posible, pero creo que eso podría no ser válido porque muchos óptimos locales codiciosos no son necesariamente el óptimo global. Entonces, ¿qué hago?

Intenté buscar una respuesta en Internet antes de publicar esto y todo lo que pude encontrar es esto: http://mathforum.org/library/drmath/view/52261.html ¿Es un razonamiento erróneo? No pude entenderlo después de hablar de la descomposición en ciclos.

Gracias por cualquier ayuda

Answer 1

Esto no es cierto si el gráfico no es simple, por ejemplo tome un solo vértice y un bucle, hay una arista, pero su límite es igual a cero.

Por otro lado, si el gráfico en cuestión es sencillo, he aquí algunas pistas:

• WLOG puede suponer que su gráfico es un único componente conectado.
• Tome algún árbol de extensión de la misma, tendrá $n-1$ bordes allí.
• Te quedas con más de $\lfloor \frac{n-1}{2} \rfloor$ aristas, pero observa que no puedes añadir ningún vértice (el árbol de expansión los toca a todos), por lo tanto, cualquier borde que añada producirá un ciclo (al menos uno).
• Ninguna arista puede ser compartida entre ciclos, ya que esto crearía un ciclo par (esto significa que cada arista que añadas creará un ciclo, pero no debe crear dos o más).
• Lo mejor que puedes hacer es formar triángulos (los ciclos Impares más pequeños posibles), pero no puedes obtener más de $\lfloor\frac{n-1}{2}\rfloor$ (para cualquiera de las aristas restantes se necesitan dos del árbol de expansión), por lo que no se pueden añadir más aristas.

Espero que le sirva de ayuda ;-)