GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
57 views
maximum number of edges in a simple planar graph with 10 vertices which contains no triangle is?
asked in Graph Theory by Junior (809 points)   | 57 views

2 Answers

+4 votes
Best answer

There is a standard result regarding this :

If the graph is connected simple planar graph and it contains no triangles , then no of edges e should satisfy :

e <= 2n - 4

Hence given n = 10 ,

The maximum no of edges in such graph  =  2*10 - 4 

                                                             =  16 

 

EDIT : Proof of the given result :

Let we have f faces and as we are given that no triangle should be present in the graph , hence minimum no of edges will be 4 in each face..Also each edge will be counted twice as it will serve as an edge for 2 faces..Hence we have :

         e  >=  4f/2  = 2f

==>   f  <=  e/2         .........(1)

Now as the graph is planar so Eulers theorem holds ..

We know , if a graph is connected and planar ,

        f   =   e - n + 2        ..........(2)

From  (1) , we have :

        f  <=  e/2  

==>  e - n + 2  <=  e/2

==>  e - e/2    <=   n - 2

==>  e        <=   2n -  4

answered by Veteran (77.2k points)  
selected by
please prove the result or give me some source of the proof
proof by 4 color theorem
what if it can contain triangles?
If we consider triangles , we will have e <= 3n - 6..

In that case , e >= 3f/2  as each face has minimum of 3 edges..Now proceed in the same way as I did in the proof..
+1 vote

using the euler formula....

for any simple planer graph...

 

v-e+r=2  kr<=2*e  ,r<=2e/k  

put the value.....e 

v-e+2e/k>=2.....v-e(1-2/k)>=2.....v-2>=e(1-2/k)....(v-2)/(k-2/k).......(v-2)(1+2/(k-2))....8*(1+2/(k-2))....for maximum,k-2 must be minimum...i.e(k=4) k must be minimum.i.e=16

here k is the region having min degree....

answered by Active (1.1k points)  


Top Users Sep 2017
  1. Habibkhan

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,164 questions
33,742 answers
79,994 comments
31,125 users