Un gráfico G = (V, E) satisface |E| ≤ 3 |V| – 6. El grado mínimo de G se define como 
. Por lo tanto, el grado mínimo de G no puede ser
(A) 3
(B) 4
(C) 5
(D) 6
Respuesta: (D)
Explicación:
Sea x el grado mínimo de G, entonces G tiene al menos |v| *x/2 aristas.
|v|*x/2 <= 3* |v| -6
para x=6, obtenemos 0 <= -6, por lo tanto, el grado mínimo de G no puede ser 6.
Por lo tanto, la respuesta es (D).
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA