Just additional information --

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

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

Dark Mode

24,544 views

37 votes

6

edited
Nov 4, 2022
by JAINchiNMay

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$

18

1

47 votes

Best answer

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$.

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$.

18 votes

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.

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.