2024-133

Considere as afirmações abaixo sobre um grafo simples G.

I) Se \(G\) é uma árvore com \( n(G) \geq 3 \), então \( 2 \leq diam(G) \leq n(G)-1 \), onde a igualdade \( 2 = diam(G) \) é válida se, e somente se, \(G\) é uma estrela e a igualdade \( diam(G) = n(G)-1 \) é valida se, e somente se, \( G = P_{n} \).

II) \( raio(G) \leq diam(G) \), com igualdade se, e somente se, todo vértice de \(G\) tem a mesma excentricidade.

III) Considere o grafo abaixo:

Este grafo tem exatamente 4 árvores espalhadas.

Das afirmações, são verdadeiras exatamente:

a) I, II

b) I, III

c) II, III

d) I, II, III

e) NDA

Ideia Original de: Gabriel Cruz Vitale Torkomian