Teorema 18.1.

Un multigrafo conexo G = (V, E) contiene una cadena euleriana (ciclo euleriano) si y sólo si el número de vértices con grado impar es 2 (0).

Demostración

⇒ Si existe una cadena euleriana, los vértices con grado impar son los extremos. En el caso del ciclo, no hay vértices con grado impar. Es suficiente con ir sumando el grado al recorrer la cadena o el ciclo eulerianos. ⇐ La demostración de esta implicación se hace por inducción en el número de aristas. Se supone que hay Seguir leyendo “Teoremas y demostraciones matemáticas” »