[SENIOR 2006 - C3] Contare i cicli Hamiltoniani

[MindFlyer]

Sia G un grafo in cui ogni vertice ha grado dispari. Dimostrare che ogni arco di G appartiene ad un numero pari di cicli Hamiltoniani distinti.

[MindFlyer]

Definizioni: un ciclo Hamiltoniano è un cammino nel grafo che parte da un nodo, tocca una ed una sola volta tutti gli altri nodi, e torna al punto di partenza.

I suggerimenti che ho dato allo stage sono questi: sia G=(V,E), si prenda un arco (x,y), e si consideri l'insieme H di tutti i cammini (non cicli!) Hamiltoniani nel grafo (V,E\{(x,y)}) che partono da x. Si costruisca un grafo su H, collegando i cammini che possono essere trasformati l'uno nell'altro opportunamente. Si utilizzi infine il noto teorema sulla parità dei nodi di grado dispari in un grafo.

EDIT: fatta un po' di pulizia nel thread.