Ciclos e Caminhos Longos em Grafos Ímpares

O grafo impar Ok e o grafo cujos vertices sao todos os subconjuntos de tamanho k de um conjunto com (2k+1) elementos e dois vertices sao adjacentes se eles sao disjuntos. Uma conjectura atribuida a Biggs afirma que o grafo Ok e hamiltoniano para k > 4 e uma conjectura atribuida a Lovasz implica que Ok tem um caminho hamiltoniano para k > 2. A partir de um ciclo hamiltoniano em Ok-1, mostramos como construir um ciclo em Ok com pelo menos 75% dos vertices de Ok. Adicionalmente, nos provamos que, para todo k, o grafo impar tem um caminho com pelo menos 50% dos vertices de Ok.