CGU-NET | UGC NET CS 2018 Dic – II | Pregunta 38

Si un grafo (G) no tiene bucles ni aristas paralelas y si el número de vértices (n) en el grafo es n≥3, entonces el grafo G es hamiltoniano si

(i) deg(v) ≥n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.
(iii) E (G) ≥ 1/3 (n − 1 )(n − 2 ) + 2 

(A) (i) y (iii) solo
(B) (ii) y (iii) solo
(C) (iii) solo
(D) (ii) solo

Respuesta: (D)
Explicación: En un gráfico hamiltoniano (G) sin bucles y bordes paralelos:

• De acuerdo con el teorema de Dirac en un grafo de vértices, grado (v) ≥ n / 2 para cada vértice de G.
  Entonces, la afirmación (i) es falsa.
• Según el teorema de Ore grado (v) + grado (w) ≥ n para todo n y v no conectados por una arista es condición suficiente para que un gráfico sea hamiltoniano.
  Entonces, la declaración (ii) es Verdadera.
• 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.
  Entonces, la afirmación (iii) es falsa.

La opción (D) es correcta.
Cuestionario de esta pregunta