Re: [obm-l] problema do caminhao

["Domingos Jr." <dopikas@xxxxxxxxxx>]

>Se você estudou teoria dos grafos, pode notar que o
>problema pede para provar a existência de um caminho
>(ciclo) hamiltoniano nesse grafo que é cúbico. Se não
>me engano (pode ser que eu esteja enganado), todo
>grafo conexo cúbico (todo vértice tem grau 3) admite
>um ciclo hamiltoniano.
>  
>
Isso é falso... até mesmo se nos restringirmos a grafos cúbicos 
bipartidos 3-conexos, veja
http://mathworld.wolfram.com/BicubicGraph.html

Há a seguinte conjectura em aberto
http://mathworld.wolfram.com/BarnettesConjecture.html

[ ]'s
=========================================================================
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
=========================================================================