816 views
1 votes
1 votes
maximum number of edges in a simple planar graph with 10 vertices which contains no triangle is?

2 Answers

Best answer
5 votes
5 votes

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

selected by
1 votes
1 votes

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

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
0 votes
0 votes
1 answer
3
Dhiraj_777 asked May 4, 2023
488 views
In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?
0 votes
0 votes
1 answer
4
Sahil_Lather asked Apr 15, 2023
439 views
Graph G is obtained by adding vertex s to $K_{3,4}$ and making s adjacent to every vertex of $K_{3,4}$ .The find the minimum number of colours required ot edge-colour is ...