Na tarefa 9, como o grafo G tem delta(G) >= n(G) - 2, no pior caso qualquer vértice não será vizinho de somente outros dois vértices, ou seja alfa(G) <= 3. Correto?
Dúvida: se alfa(G) <= 3 para todo grafo com n(G) >= 4, posso utilizar do exercício que foi dado em sala de aula, onde mostra que se alfa(G) <= n/2, G é hamiltoniano?
É claro que precisa explicar melhor e com mais detalhes, mas a idéia central é que alfa(G) será sempre menor ou igual que n/2, logo G é hamiltoniano.
É verdade que
alfa(G) > n/2 implica G não-hamiltoniano
mas NÃO É VERDADE que
alfa(G) <= n/2 implica G hamiltoniano.
Cuidado om esse tipo de conclusão precipitada!
alfa(G) > n/2 implica G não-hamiltoniano
mas NÃO É VERDADE que
alfa(G) <= n/2 implica G hamiltoniano.
Cuidado om esse tipo de conclusão precipitada!