[carambola]

Sea $$G$$ un grafo conexo euleriano y sea $$\{A,B\}$$ una partición de $$V(G)$$. Probad que el número de aristas con un extremo sobre $$A$$ y el otro sobre $$B$$ es par.

[geómetracat]

La idea es la siguiente. El grafo tiene un ciclo euleriano, es decir, un camino que empieza y acaba en el mismo vértice y que pasa exactamente una vez por cada arista del grafo. Cada vez que atravesamos una arista con un extremo en \[ A \] y otro en \[ B \] cambiamos de conjunto de la partición. Pero como el camino es cerrado, al final debemos haber cambiado un número par de veces, para acabar en el mismo conjunto en el que empezamos. Como el ciclo pasa exactamente una vez por cada arista, el número de aristas que unen un extremo de \[ A \] y uno de \[ B \] debe ser par.

[math_cramer]

Respecto a tu idea de la demostración tengo una duda, no aceptamos multigrafos no? porque sino un grafo G con un punto y una aresta que va del punto a si mismo si que cumpliria las hipotesis (dado que podriamos pensar la partición A como solo un punto y la partición B como el vacío) y sin embargo el numero de arestas (1) no seria par.

PD: perdón si no uso Latex, es que aún no lo se usar bien del todo y como no he necesitado de ningun caracter especial he pensado que no pasa nada si no uso Latex.

Edit: no se como de "legal" es hacer una partición con el vacío ya que si no recuerdo mal creo que para toda partición en componentes connexas deberia tener cada punto de A como mínimo una aresta con un punto de B, y hacer una aresta con el vacío no suena muy bien...

[geómetracat]

Pues cuando respondí pensé solo en grafos usuales (no en multigrafos), pero yo diría que la demostración funciona igual.
Funciona incluso si uno de los conjuntos de la partición (digamos \[ B \]) es vacío, pues en ese caso el número de aristas que unen un vértice de \[ A \] con uno de \[ B \] es cero, que es par. Claro que en este caso no hace falta ni asumir que existe un ciclo euleriano.

[math_cramer]

Ostras ahora leyendolo más detenidamente me he dado cuenta de cual fue mi error, la proposición habla sobre el numero de aristas de A hasta B y no de cuantas aristas tiene el grafo  .
Muchas gracias por la respuesta 
PD: Creo que como bien tu dices, la demostración seria la misma porque seria como si considerases el multigrafo \( \overline{G} \) definido como el multigrafo G sin las aristas que tuviesen los dos vértices en la misma partición y entonces se ve claro que para salir y volver al conjunto de la partición hay que hacer un número par (no negativo) de pasos (donde considero que quedarse quieto es dar 0 pasos).