in Graph Theory edited by
23,972 views
37 votes
37 votes
The maximum number of edges in a bipartite graph on $12$ vertices is____
in Graph Theory edited by
24.0k views

4 Comments

Just additional information --

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

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
18
Put equal number of verices on both the sides, and connect each vertex of bucket1 with all vertices of bucket2

$6*6=36$ edges.
1
1
@Kushagra gupta

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

8 Answers

46 votes
46 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$.
edited by

2 Comments

How many number of bi-partite graphs are possible for N vertices?
0
0
1
1
18 votes
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.
4 votes
4 votes
max no. of edges in BIPARTILE GRAPH with "n" vertex = floor[(n^2)/4]
3 votes
3 votes

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 !
2
2
Answer:

Related questions