+1 vote
101 views
maximum number of edges in a simple planar graph with 10 vertices which contains no triangle is?
asked | 101 views

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 (100k points)
selected
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 Boss (7.8k points)