[obm-l] Problema 6 - OBM 3a. fase - Nível 2

[Cesar Ryudi Kawakami <cesarkawakami@xxxxxxxxxx>]

Sei que a solução envolve conhecimento do princípio indutivo e da 
interpretação de gráficos, mas...

Como resolver?

"PROBLEMA 6:
Há N cidades na Tumbólia. Cada duas cidades desse país são ligadas por uma 
rodovia ou uma ferrovia, não existindo nenhum par de cidades ligadas por 
ambos meios.
Um turista deseja viajar por toda Tumbólia, visitando cada cidade 
exatamente uma vez, e retornar a cidade onde ele começou sua jornada.
Prove que é possível escolher a ordem na qual as cidades serão visitadas de 
modo que o turista mude o meio de transporte no máximo uma vez."

Eu sinceramente não fazia a mínima noção de como resolver esse problema... 
No segundo dia de prova, resolvi as questões 4 e 5 em pouco tempo, mas 
empaquei nesta... =(

Um abraço,

Cesar Ryudi Kawakami

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================