MO405 - Questão para a prova oral

Número: 007

Enunciado: Considere as seguintes afirmações sobre os conceitos fundamentais de grafos.  Quais delas estão corretas?:

I - Um grafo simples não possui ciclos nem arestas múltiplas.
II - A matriz de incidência de um grafo simples é sempre binária (possui somente 0's e 1's).
III - Um grafo é k-partido se e somente se o número cromático é no mínimo k.
IV - O grafo de Petersen possui entre outras propriedades: cintura (girth) de tamanho 5, 10 vértices de grau 3, 15 arestas.

1. somente I. II e III
2. somente I, II e IV
3. somente II e III
4. somente II e IV
5. NDA

Idéia original de: Gustavo Waku