PUERTA | GATE-IT-2004 | Pregunta 37

¿Cuál es el número de vértices en un grafo conexo no dirigido con 27 aristas, 6 vértices de grado 2, 3 vértices de grado 4 y el resto de grado 3?
(A) 10
(B) 11
(C) 18
(D) 19

Respuesta: (D)
Explicación: La idea es usar Handshaking Lema : – En cualquier gráfico, la suma de todos los vértices-grado es igual al doble del número de bordes

Let x = Total Number of Vertices.

By Handshaking Lemma

6*2 + 3*4 + (x-9)*3 = 27*2

24 + (x-9)*3 = 54

x-9 = 10

x = 19 

Cuestionario de esta pregunta