1. 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.
  2. Um grafo simples bipartido não tem ciclos de comprimento 5. Certo. Mais geralmente não tem ciclos de comprimento ímpar.
  3. 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.
  4. 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.