The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote
maximum number of edges in a simple planar graph with 10 vertices which contains no triangle is?
asked in Graph Theory by Active (1.6k points) | 101 views

2 Answers

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

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,170 questions
40,847 answers
39,703 users