Ci sei abbastanza vicino, ma così non funziona. Un motivo è appunto il fatto che scarti l'ipotesi che sia connesso
Infatti, se prendi due triangoli disgiunti, uno avrà almeno 2 archi pari.
Se a un vertice sono attaccati due numeri consecutivi, ok, quel vertice funziona. Però quando scegli un vertice a caso da cui iniziare il tuo percorso, ecco, è quel vertice che ti può dar problemi!
Quindi la strategia giusta è: intanto è sufficiente fare i grafi senza vertici di grado 1. Poi scelgo un vertice a caso e da lui inizio un percorso a caso, numerando 1,2,... gli archi su cui passo, e mi fermo quando passo per un vertice già toccato.
Poi, tra i vertici che ho già toccato, scelgo uno da cui pare un arco ancora non colorato, e continuo un percorso a caso da lì finchè non tocco un vertice già toccato. E così via.
L'algoritmo funziona perchè finisco se e soltanto se ogni vertice già toccato ha tutti gli archi colorati, e per l'ipotesi che è connesso, se e soltanto se ho colorato ogni vertice.
La colorazione è buona perchè ogni vertice o lo ho toccato per la prima volta formando un percorso che non si è fermato lì, e quindi è attaccato a due numeri consecutivi coprimi, oppure è il primo vertice che ho toccato, ma a questo ho dato il numero 1 che è il "jolly".
