PUERTA | GATE-CS-2015 (Conjunto 1) | Pregunta 65 – Part 10

Sea G un grafo plano conexo con 10 vértices. Si el número de aristas en cada cara es tres, entonces el número de aristas en G es _______________.
(A) 24
(B) 20
(C) 32
(D) 64

Respuesta: (A)
Explicación: La fórmula de Euler establece que si se dibuja un gráfico plano finito, conectado, en el plano sin ninguna intersección de bordes, entonces

    v − e + f = 2.  
    v -> Number of vertices
    e -> Number of edges
    f -> Number of faces

As per the question 
v = 10
And number of edges on each face is three
Therefore, 2e = 3f  [Note that every edge is
                    shared by 2 faces]

Putting above values in v − e + f = 2
10 - e + 2e/3 = 2
e = 3*10 - 6 = 24

Cuestionario de esta pregunta