MO405 - Questão para a prova oral

Número:

Enunciado: Seja L(G) o grafo linha de um grafo G. Qual das implicações abaixo é falsa?

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

b) Se G é um K₄, então n(G) + e(G) = n(L(G)) + e(L(G)), onde n(G) é o número de vértices e e(G) é o número de arestas de um grafo 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