edited by
26,912 views
38 votes
38 votes
The maximum number of edges in a bipartite graph on $12$ vertices is____
edited by

9 Answers

Best answer
48 votes
48 votes
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
19 votes
19 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.
2 votes
2 votes

no. of vertics =12

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

Answer:

Related questions

42 votes
42 votes
6 answers
1
go_editor asked Sep 28, 2014
17,334 views
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
100 votes
100 votes
10 answers
2
57 votes
57 votes
11 answers
3
go_editor asked Sep 28, 2014
18,196 views
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?$\left\lfloor\frac {n}{k}\right\rfloor$$\left\lceil \frac{n}{k} \right\r...
32 votes
32 votes
9 answers
4
makhdoom ghaya asked Feb 13, 2015
24,386 views
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.