44 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
closed as a duplicate of: GATE2015-1_54
closed | 44 views

#edges <= 24.

by euler's formula,

# regions/faces = e-v+2

$\sum deg(r) = 2\left | edges \right |$

if the no.of edges in the face is 3, then total no.of edges will be = $3\left | r \right |$

$\sum deg(r) \geq 3\left | r \right |$

$2\left | e \right | \geq 3\left | r \right |$

on substituting euler's formula for r,

$2\left | e \right | \geq 3\left ( e-v+2 \right )$

$e \leq 3V-6$

Substitute the given data in the above formula.

we get

$e \leq 24$