Find maximum edges in Graph

Question

Comments

is planarity in 2016 gate syllabus?

Answer 1

maximum no. Of edges 26

In a connected planner graph with v vertices e edges r regions or faces and min. Degree of region =k (no cycle of length less than 4 means no region can have degree less than 4)

The following property should satisfy

1 v-e+r=2

2 k.r≤2e

3 e ≤ k(v-2)/(k-2)

Here k=4 v=15

maximum no. Of edges

e ≤ 2v-4

Max no. Of edges= 2*15-4= 26

Answer 2

e<=2v --4

so e<=2*15-4

e<=26

Comments

when this formula is applicable  e<= 2V - 4  ?

---

when the planar graph doesnot conatain traigle

---

when it contains no triangles

u can derive it  using 4r<=2e

v-e+r=2

---

is planarity in 2016 gate syllabus?

Answer 3

Use following lemma for planer graph,

If G = (V, E) is a planar graph with |E| ≥ g and no cycle of length < g,

then: |E| ≤ (g /(g − 2)) (|V | − 2).

Here g = 4;  hence |E| ≤ (4 /(4 − 2)) (15 − 2)  = 26.

|E| ≤ 26 => Maximum no.of edges  = 26.