MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo com número de vértice n, número de arestas e e cintura g. Assinale a expressão que corresponde à fórmula do número máximo de arestas para que o grafo G seja planar.

a) (g - 1)(n - 2) / (g - 2) ≥ e

b) g(n - g) / 2(g - 2) ≥ e

c) g(n - 2) / (g - 2) ≥ e

d) (2g + 1)(n - 2) / (g - 2) ≥ e

e) NDA

Ideia original de: Rafael de Oliveira Werneck