11 Mostre que um grafo bipartido com um número ímpar de vértices não pode ser hamiltoniano.

Para mostrar que um grafo bipartido com um número ímpar de vértices não pode ser hamiltoniano, podemos usar o seguinte raciocínio: Suponha que temos um grafo bipartido com um número ímpar de vértices. Um grafo bipartido é aquele em que os vértices podem ser divididos em dois conjuntos disjuntos, de forma que todas as arestas conectem um vértice de um conjunto ao outro conjunto. Agora, vamos supor que esse grafo seja hamiltoniano, ou seja, que exista um ciclo hamiltoniano que passe por todos os vértices do grafo exatamente uma vez. Se o grafo é bipartido, isso significa que o ciclo hamiltoniano deve alternar entre os dois conjuntos de vértices. No entanto, como o número de vértices é ímpar, não é possível alternar entre os conjuntos de forma que o ciclo passe por todos os vértices exatamente uma vez. Portanto, concluímos que um grafo bipartido com um número ímpar de vértices não pode ser hamiltoniano. Espero ter ajudado! Se tiver mais alguma dúvida, é só perguntar.