MO405 - Questão para a prova oral

Número: 064

Enunciado: Suponha que n(G), e(G) e L(G) denotem, respectivamente, o número de vértices, o número de arestas e o grafo linha de um grafo G. Qual das implicações abaixo é FALSA?

a) Se G é um K₄, então n(G) + e(G) = n(L(G)) + e(L(G)).

b) Se G é um ciclo, então L(L(G)) = G.

c) Se G é uma estrela com i folhas, então L(G) = K_i.

d) Se G é um caminho com n vértices, então L(G) é um caminho com n-1 vértices.

e) NDA