GATE CSE 1992 | Question: 01,x

Question

Maximum number of edges in a planar graph with $n$ vertices is _____

Comments

The question didn't told if graph is connected or disconnected yet we took k=1? why? 

Answer 1

Answer: 3n - 6

Ref: http://mathoverflow.net/questions/124116/maximum-number-of-edges-in-a-planar-graph

Comments

i think it is 2n-2

if n=2 then edges will be 1 it is also a planar graph but according to your equation it becomes 0

---

@ suneetha 2n-4 (not 2n-2) its true when the graph has no cycle of lenght 3.

---

they didn't represent about whether it should have cycle or not?

---

if n is even then the equation comes like 2(n-1)
if n is odd then the equation comes like 2n-1
then what is the answer for this question?

Answer 2

Consider a simple undirected connected grah $G(V, E)$ having $F$ faces and $C = 1$ components

Every Edge in graph increase the $deg(f_i) $ by $2$ by this we can say that if a graph have $|E|$ no of edges then sum of degree of all faces will be $2|E|$,

 

$$\sum deg(f_i) = 2|E|$$

A conected planner graph have at least $|V| >= 3$, and a cycle creates a face of degree 3

By handshaking theorem, the sum of all minimum degree $<= 2|E|$,  similarily

$$\sum \delta (deg(f_i)) <= 2|E|$$

 

$$3|F| <= 2|E|$$

 

$$|F| <= \frac{2|E|}{3}$$

 

add $|V|$ both side

$$|V| + |F| <= \frac{2|E|}{3} + |V|$$

 

Eular Formula

$$|V| + |F| = |E| + |C| + 1$$

for connected graph $|C| = 1 $

$$|V| + |F| = |E| + 2$$

 

Put the value of $|V| + |F|$ in Eular formula,

 

$$2 + |E| <= \frac{2|E|}{|3|} + |V|$$

 

$$ |E| <= 3|V| - 6$$

 

The Above inequality is for the planner graph having tringles, but what if graph have no trinagles ? then $deg(f_i) \neq 3$ but $>= 4$

a graph min 3 vertices that have no trainlges have 2 edges creates degree 4 for 1 and only outer face.

so the $\delta (deg(f_i)) >= 4$ and,

$$ \sum \delta (deg(f_i)) <= 2|E| $$

$$4|F| <= 2|E|$$

 

$$$|F| <= \frac{2|E|}{4}$$

 

similar to above above derivation

 

$$|E| <= 2|V| - 4$$

 

Answer 3

According to Euler's Theorem we know that 

$V+F = E+C+1$

Where V =  Number of Vertices 

F = Number of Faces

E = Number of Edges

C = Number of Connected Components 

Which gives us 

$E = V + F -(C+1)$

Now we must maximise $V+F$ and minimize $C+1$. But $V$ is given to be $n$ and minimum value of $C = 1$ when the graph is connected. Thus we get 

$E =  n + F - (1+1)$

$E = n + F - 2$

We can only maximise the number of faces by making triangles as each triangle would mean one face, to make the first triangle we would need 3 vertices and then we can make more triangles using following method : - 

Thus each of the $n-3$ remaining vertices will add 3 new faces and delete one netting +2 faces each upon further division of newly produced triangles and we initially had 2 Faces from the original triangle, from $n$ vertices we'll get maximum $2n-6+2$ = $2n-4$ faces

Maximum Number of Edges = $n + (2n-4) - 2$

= $n+2n-6$ 

= $3n-6$

 

Answer 4

For a graph containing a cycle with length three, we can use 3n-6

For a graph containing a cycle of length four, we can use 2n-4