CGU-NET | UGC NET CS 2015 junio – II | Pregunta 5

Considere un gráfico hamiltoniano (G) sin bucles y bordes paralelos. ¿Cuál de los siguientes es cierto con respecto a este gráfico (G)?
(a) grados (v) ≥ n / 2 para cada vértice de G
(b) |E(G)| ≥ 1 / 2 (n – 1) (n – 2) + 2 aristas
(c) grado (v) + grado (w) ≥ n para todo n y v no conectados por una arista.

(A) (a) y (b)
(B) (b) y (c)
(C) (a) y (c)
(D) (a), (b) y (c)

Respuesta: (C)
Explicación : En un grafo hamiltoniano (G) sin lazos y aristas paralelas:
Según el teorema de Dirac en un grafo de vértices, deg (v) ≥ n / 2 para cada vértice de G.
Según el teorema de Ore deg (v) + deg (w ) ≥ n para todo n y v no conectados por una arista es condición suficiente para que un grafo sea hamiltoniano.
Si |E(G)| ≥ 1 / 2 * [(n – 1) (n – 2)] entonces el gráfico está conectado pero no se garantiza que sea un gráfico hamiltoniano.
(a) y (c) es correcto con respecto al gráfico hamiltoniano.
Entonces, la opción (C) es correcta.
Cuestionario de esta pregunta