MO405 - Questão para a prova oral

Número:

Enunciado: Qual das afirmativas está correta:

A. Seja G um ciclo, o grafo closure de G é o próprio G.
B. Se G é um grafo simples, conexo e com uma aresta de corte e, então, G possui um caminho hamiltoniano se, e somente se, as componente de G - e possuírem um caminho hamiltoniano.
C. Se G não possui um ciclo hamiltoniano, então, o grafo linha de G também não possui um ciclo hamiltoniano.
D. K₅ é o menor grafo completo que possui dois ciclos hamiltonianos disjuntos nas arestas.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre imersão planar, podemos afirmar que:

A. Qualquer grafo planar possui uma imersão cujas faces são polígonos convexos.
B. Todo grafo planar possui K₅ como um grafo minor.
C. Se H possui crossing number igual a x e constitui um subgrafo de G, então o crossing number de G é pelo menos x.
D. O crossing number do K₆ é 2.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Qual das seguintes afirmações está correta:

A. Árvores constituem uma classe hereditária de grafos.
B. Todo cíclo é um grafo perfeito.
C. Se um grafo simples e conexo possui n vértices, m arestas, cintura c, e ao menos um ciclo, então ele não pode ser planar se m > (c(n - 2)) / (c - 2).
D. O grafo de Petersen é planar.
E. NDA.

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Sobre a coloração de vértices de grafos simples é correto afirmar que:

A. Todo grafo completo multipartido também é bipartido.
B. Se um grafo possui uma k-coloração própria então ele tem pelo menos n(n-1) arestas.
C. Todo grafo k-crítico é k-aresta-conexo.
D. Todo grafo simples com número cromático χ possui um Kχ como subgrafo.
E. NDA.

Ideia original de: Lucas