MO405 - Questão para a prova oral

Número:

Enunciado: Seja S_n o grafo estrela com n + 1 vértices. Este grafo possui um graceful labeling se, e somente se, o seu vértice central for rotulado como:

A. 0
B. 1
C. n - 1
D. 0 ou n - 1
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com grau mínimo 10. Qual dos seguintes grafos podemos afirmar certamente que sempre será um subgrafo de G ?

A. K₁₁
B. K_5,5
C. Um grafo simples conexo e acíclico com 10 arestas
D. Um grafo simples com 10 cíclos
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Seja G um grafo simples com n vértices. Considere que d(G) e D(G) são, respectivamente, o grau mínimo e máximo de G. Dado o grafo complementar de G, denotado por H, podemos afirmar que d(H) e D(H) correspondem, respectivamente, à:


A. d(G) e D(G)
B. n - d(G) e n - D(G)
C. n - D(G) e n - d(G)
D. n - D(G) - 1 e n - d(G) - 1
E. NDA

Ideia original de: Lucas

MO405 - Questão para a prova oral

Número:

Enunciado: Dado um grafo G com n vértices, qual a maior quantidade de arestas que um subgrafo acíclico de G pode ter ?

A. n² - n
B. n² / 2
C. n / 2
D. n -1
E. NDA

Ideia original de: Lucas