23,972 views
The maximum number of edges in a bipartite graph on $12$ vertices is____

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.

Maximum no. of edges occur in a complete bipartite graph i.e. when every vertex has an edge to every opposite vertex.

Number of edges in a complete bipartite graph is $mn$, where $m$ and $n$ are no. of vertices on each side. This quantity is maximum when $m = n$ i.e. when there are $6$ vertices on each side, so answer is $36$.

How many number of bi-partite graphs are possible for N vertices?
in a bipartite graph all the vertices can be distributed in two sets .let the set-1 has M vertices and set-2 has N vertices.

as  M+N=12

total no of edges =MN =M(12-M)

take the derivative of this  equation  with respect to M.

d(total no of edges)/d(M)= 12-2M

second order derivative is negative so this function will attain maximum value at 12-2M=0

so M=6

and N=6

total no of edges = MN= 36.
by
max no. of edges in BIPARTILE GRAPH with "n" vertex = floor[(n^2)/4]

no. of vertics =12

max. no of edges=floor((12*12))/4=36

### 1 comment

This is not wrong answer . if we divide total number of vertices into 2 parts (equal parts ) n/2 each

Then maximum no of edges would be n/2*n/2 = 144/4 = 36 .

this is same as what @arjun sir has selected the answer !

1
13,556 views