Cierto árbol tiene dos vértices de grado 4, un vértice de grado 3 y un vértice de grado 2. Si los otros vértices tienen grado 1, ¿cuántos vértices hay en el grafo?
(A) 5
(B) n – 3
(C) 20
(D) 11
Respuesta: (D)
Explicación: Hay 2 vértices de grado 4, 1 vcertex de grado 3, 1 vcertex de grado 2 y el vértice de grado uno es desconocido.
Supongamos que k es el vértice nof de grado uno.
Vértice total = 2 + 1 + 1 + k = k + 4.
Número de aristas = vértice – 1,
es decir, k + 4 – 1
= k + 3.
Ahora aplique el lema del apretón de manos (para obtener más información sobre el lema del apretón de manos, consulte: Lema del apretón de manos e Interesante Propiedades del árbol)
2 * 4 + 1 * 3 + 1 * 2 + 1 * K = 2 * (No de aristas)
es decir, 13 + k = 2 * (k + 3)
k = 7.
Vértice total = 7 + 4 = 11.
Entonces , la opción (D) es correcta.
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