The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+21 votes
The maximum number of edges in a bipartite graph on $12$ vertices is____
asked in Graph Theory by Veteran (99.8k points)
edited by | 3k views
Just additional information --

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

5 Answers

+31 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$.
answered by Boss (11.2k points)
edited by
How many number of bi-partite graphs are possible for N vertices?
+9 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.
answered by (209 points)
+3 votes

no. of vertics =12

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

answered by (59 points)
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 !
+3 votes
max no. of edges in BIPARTILE GRAPH with "n" vertex = floor[(n^2)/4]
answered by Active (4.3k points)
+1 vote

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.

answered by Loyal (8.3k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,009 questions
45,506 answers
48,693 users