GATE CSE 2014 Set 2 | Question: 3

Question

The maximum number of edges in a bipartite graph on $12$ vertices is____

Comments

Just additional information --

For same perimeter rectangles  square has highest area.(n1+n2 = n then n1*n2 is max iff n1==n2)

---

Maximum number of edges in a $bipartite\ graph$ with $n$ vertices $=\left \lfloor{\dfrac{n^2}{4}}\right\rfloor$

Proof:

• Let on one side $k$ vertices & then on the other side there will be $(n-k)$ vertices (assumed)
• Total number of edges $=k(n-k)$ 

Let's maximise this value:

$\\\frac{\partial }{\partial x}(kn-k^2)=0, \\\\n-2k=0 ,\\\\ \dfrac{n}{2}=k$

---

  $\frac{\partial^2 }{\partial x^2}(kn-k^2)\\ \\ =-2<0$  

means at $k=\dfrac{n}{2}$ maximum edges will be present.

---

$Ans: =\left \lfloor{\dfrac{12^{2}}{4}}\right\rfloor=36$

---

Put equal number of verices on both the sides, and connect each vertex of bucket1 with all vertices of bucket2

$6*6=36$ edges.

---

@Kushagra gupta

bro, your comment is eligible for best answer. So, please write an answer with same content as you written in comment.

Answer 1

Number of edges would be maximum when there are 6 edges on each side and every vertex is connected to all 6 vertices of the other side.

Answer 2

This content is copy of comment of @Kushagra gupta 

Maximum :-  number of edges in a $bipartite\ graph$ with $n$ vertices $=\left \lfloor{\dfrac{n^2}{4}}\right\rfloor$

Proof:

• Let on one side $k$ vertices & then on the other side there will be $(n-k)$ vertices (assumed)
• Total number of edges $=k(n-k)$ 

Let's maximise this value:

$\\\frac{\partial }{\partial x}(kn-k^2)=0 \\\\n-2k=0 \\\\ \dfrac{n}{2}=k$

---

  $\frac{\partial^2 }{\partial x^2}(kn-k^2)\\ \\ =-2<0$  

means at $k=\dfrac{n}{2}$ maximum edges will be present.

---

$Ans: =\left \lfloor{\dfrac{12^{2}}{4}}\right\rfloor=36$

Answer 3

For maximum edges, the bipartite graph can be complete bipartite graph, hence 6^2=36 edges.

Answer 4

n is even so n/2*n//2 = 6*6 = 36