3.1k views
The maximum number of edges in a bipartite graph on $12$ vertices is____
edited | 3.1k views
+2

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

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$.
edited by
0
How many number of bi-partite graphs are possible for N vertices?
0
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.
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
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 vote