- Se todos os vértices de um grafo conexo têm grau
4 então o grafo admite ciclos
hamiltonianos. Falso. É correcta a afirmação
analoga sobre ciclos eulerianos.
- Um grafo simples bipartido não tem ciclos de comprimento
5. Certo. Mais geralmente não
tem ciclos de comprimento ímpar.
- Um grafo de ordem 8
pode ter grafos parciais de ordem
4. Falso. Um grafo parcial
de outro grafo tem sempre os mesmos vértices, e portanto
a mesma ordem.
- Se um vértice num grafo simples tem grau
4 então o índice cromático desse
grafo é maior ou igual a 4. Exacto.
O índice cromático de um grafo
é sempre maior ou igual ao maior grau de vértice
nesse grafo.