GATE CSE
First time here? Checkout the FAQ!
x

graph [closed]

0 votes
50 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
asked in Graph Theory by Junior (695 points)  
closed by | 50 views

1 Answer

0 votes

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

 

 

 

answered by Active (1.2k points)  

Related questions

+1 vote
0 answers
1
asked ago in Graph Theory by charul (25 points)   | 42 views
+1 vote
1 answer
2
+1 vote
1 answer
3


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4130 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2916 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,209 comments
30,083 users