[Squee]

Sea \( G \) un grafo simple y \( D \) una orientación fuertemente conexa de G. Probar que si \( G \) tiene un ciclo impar, entonces \( D \) tiene un ciclo dirigido impar.

Intento de demostración:
Para todo ciclo impar, he de tener como mínimo dos aristas en la misma dirección, dado que no pueden alternarse siempre (si se alternan siempre termina teniendo el último arista la misma dirección que la primera, y como es un ciclo están pegados).

Para un ciclo de longitud 3, tengo dos posibilidades:
Las tres aristas en la misma dirección (entonces hay un ciclo dirigido, y es trivial).
Tengo dos aristas en la misma dirección y una en la otra dirección.
Tomo los dos vértices que determinan la 1ra y tiene que existir un ciclo dirigido en el cual este contenida por ser \( D \) fuertemente conexa. Si este es impar, ya tenemos nuestro ciclo dirigido.
Si es par, le saco la arista que posee y la agrego las otras dos del ciclo, de forma que sigue siendo un ciclo dirigido y ahora es impar.

Me cuesta generalizarlo para longitudes arbitrarias. Tengo un intento:
En cada arista del ciclo impar voy verificando si pertenece a algún ciclo, si este es impar ya esta, así que asumo que son pares. De tal forma tengo una cantidad impar de aristas que están "solas" sin ninguna otra consecutiva o precedente en la misma dirección, y por lo menos una de longitud 2.

Por cada conjunto de aristas de nuestro ciclo en la misma dirección, creo un ciclo. Estos son todos pares. Les saco las aristas pertenecientes a nuestro ciclo de forma que termino sumando longitudes pares y restandole una longitud impar (nuestro ciclo).
El problema es que eso no necesariamente me da un ciclo ya que puedo repetir aristas, y no estoy seguro de como descontarlas.

¿Alguna sugerencia?
(No se me ocurre una forma clara de explicarlo sin dibujitos, y no tengo scanner a mano)

[Luis Fuentes]

Hola

Sea \( G \) un grafo simple y \( D \) una orientación fuertemente conexa de G. Probar que si \( G \) tiene un ciclo impar, entonces \( D \) tiene un ciclo dirigido impar.

Considera un ciclo impar, fija una dirección para recorrerlo y considera todas los tramos que están en sentido contrario:

1) Si no hay ninguno has terminado.

2) Para cada una de ellos por ser fuertemente conexo, existe un ciclo dirigido que la contiene: si es de longitud impar has terminado.

3) Si todos los ciclos dirigidos que contienen a esos tramos son de longitud par, para cada un de ellos si el ciclo dirigido que los contiene es de longitud par \( n \), entonces si el tramo tiene longitud \( l \), podemos sustituirlo por las \( n-l \) aristas restantes del ciclo dirigido, de forma que \( n-l \) y\(  l \) tienen la misma paridad.

Por tanto habremos construido un nuevo ciclo donde todos los tramos en sentido opuesto han sido sustituidos por otros en la misma orientación y con un número de aristas igual en paridad: tal ciclo es dirigido y tienen longitud impar.

Saludos.

[Squee]

¿Que pasa si dos de los ciclos cuyas aristas adjunto al ciclo inicial (para reemplazar las que tienen dirección contraría a la necesaria) comparten algún vértice o arista?

Editado: No se si entendí bien tu idea o no y eso capaz no puede pasar, pero creo que entendí como combinarlos y borrar las aristas restantes para conservar paridad o forzar lo que necesite.
Si consigo clarificar la idea la posteo.

Una vez construido un ciclo de la forma en la cual lo construyo manco, tenemos dos casos posibles:
a) Que sea realmente un ciclo, es decir, que realmente sea un camino simple cerrado.
b) Que no lo sea
Si no lo es, supongamos que se corta al menos un par de ciclos.
Si un fue construido para ir de \( v_{1} \) a \( v_{2} \) (con \( v_{1},v_{2} \) en el ciclo impar original) y el otro de \( v_{3} \) a \( v_{4} \), entonces a partir del primer vertice en el cual el 1er ciclo se intersecta con el 1ro, le saco sus aristas. Analogamente con las aristas anteriores al último vertice en el cual coincide el segundo ciclo con el 1ro.
Entonces me quedan un camino de \( v_{1} \) a \( v_{4} \).
Esto puede o no alterarme la paridad. Si lo hace, es porqué las aristas que removí, que a su vez forman un ciclo, forman un ciclo impar.
Y si no lo hacen, la demostración anterior del teorema no se ve alterada. Lo repito con cada ciclo del nuevo grafo que se intersecte hasta terminar con estas intersecciones.

[Luis Fuentes]

Hola

¿Que pasa si dos de los ciclos cuyas aristas adjunto al ciclo inicial (para reemplazar las que tienen dirección contraría a la necesaria) comparten algún vértice o arista?


Editado: No se si entendí bien tu idea o no y eso capaz no puede pasar, pero creo que entendí como combinarlos y borrar las aristas restantes para conservar paridad o forzar lo que necesite.
Si consigo clarificar la idea la posteo.

Si, puede pasar que no sea un ciclo y en el proceso que describo se repitan vértices o aristas. Pero es muy fácil concluir a partir de ahí. Lo que tenemos con toda seguridad es un camino dirigido de longitud impar, que comienza y termina en el mismo vértice. Se descompone en unión de varios ciclos dirigidos. Si todos fuesen de longitud par, el camino total también tendría longitud par.

Saludos.