Si una gráfica tiene un ciclo de Euler, ¿los componentes biconéctados también tienen ciclos de Euler?
9
Si una gráfica tiene un ciclo de Euler, ¿los componentes biconéctados también tienen ciclos de Euler?
Respuestas:
Si. Si comienza con un ciclo de Euler para el gráfico y se restringe a un componente conectado, entonces lo que tiene es un ciclo en el componente conectado (básicamente, si el ciclo de Euler deja el vértice v en el componente conectado, entonces sabe que debe regresar al componente biconnectado a través de v, de lo contrario podríamos agrandar nuestro componente biconnectado, contradiciendo su maximalidad).
fuente