GATE CSE 2015 Set 1 | Question: 54

Question

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_______________.

Comments

Planarity is in syllabus?

---

@Arjun Sir, although not explicitly mentioned in the syllabus, questions have appeared from planarity recently.

Eg: GATE CSE 2021 Set 1 | Question: 16 - GATE Overflow for GATE CSE

 

---

Possible configuration based upon the given conditions. Edges = 24

Answer 1

#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$

Answer 2

Use Formula ( also v => 3 )

     e <= 3V-6

     at V=10 , we get e = 24

  is this approach fine??

Answer 3

We can simply use that No of edges in the planar graph <=  3(no of vertices) – 6

It gives , No of edges <=  24  

Answer 4

r=e-v+2     ------(1)

since each face has 3 edges so degree of each face is 3

total degree of all faces=2*no of edges

3*no of faces=2*no of edges

3r=2e   --------(2)

substituting (2) in (1)

2e/3=e-v+2

e/3=v-2

e=3v-6

e=3*10-6

e=30-6

e=24