Question

The maximum number of edges in a bipartite graph on 12 vertices is

• A. 36

Answer 1

The correct option is A 36
Bipartite graph {u, v} where u and v are partition on vertices:

(a) $\{1,11\}\Rightarrow 1\times 11=11\text{edges maximum}$

(b) $\{2,10\}\Rightarrow 2\times 10=20\text{edges maximum}$

(c) $\{3,9\}\Rightarrow 3\times 9=27\text{edges maximum}$

(d) $\{4,8\}\Rightarrow 4\times 8=32\text{edges maximum}$

(e) $\{5,7\}\Rightarrow 5\times 7=35\text{edges maximum}$

(f) $\{6,6\}\Rightarrow 6\times 6=36\text{edges maximum}$

$\therefore$ Maximum number of edges in a bipartite graph on 12 vertices = 36 edges.