Planar Graphs | Graph Theory | Selfdoubt

Question

In a Connected Planar Bipartite Graph of order 10 atmost how many edges be present ?

Answer 1

From Euler Formula We know for connected graph having $v$ vertices ,$e$ edges,$f$ faces ,

$v-e+f=2$.

In problem it is given ,

$v=10$

Given graph is bipartite , which implies The is no odd length cycle in the graph => There is no triangle in the graph => every face must bounded by at least 4 edges.

And we know that, degree summation of each face= $2*e$.

So we can write ,

    $4f <=2e$

or, $2f<=e$

or, $2(2+e-v)<=e$

or ,$4+2e-2v<=e$

or,$e<=2v-4$

Here it is given $v=10$

So, maximum number of edges possible , $2*10-4=16$

So ,Atmost 16 edges possible .

Comments

We are considering here face bounded by atleast 4 edges,suppose if some graph contain 5 edge cycle then that graph also included.As bipartite graph not contain any odd length cycle we have to Discard all odd length cycle possibilities ?