GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 23

Question

The maximum number of edges in a bipartite graph with $19$ vertices is _________

Answer 1

If $n$ is even, then complete bipartite graph $K_{\frac{n}{2},\frac{n}{2}}$ has maximum edges, which equals $\dfrac{n^{2}}{4}$.

If n is odd, then $K_{\frac{n-1}{2},\frac{n+1}{2}}$ has maximum edges which is $\left(\dfrac{n-1}{2}\right)\cdot \left(\dfrac{n+1}{2}\right)=\dfrac{n^{2}-1}{4}.$

Here, $n=19$ is odd, then $K_{9,10}$ has maximum edges which is $\dfrac{19^{2}-1}{4}=90$.

So, the correct answer is $90.$

Answer 2

One Fact you should remember from 12th standard NCERT..

If we are given :

a + b = n

to maximize a×b, we should have a=b

so $a = \frac{n}{2}$.

if N is odd, take a and b such that $\left | a - b \right | = 1$

Another way to state the same thing is,

Given the parameter of a rectangle, for maximum area we must have a square. (or as close as possible to square)

---

Now to this qn,

n = 19

closest to square we could get is a=10, b =9

max ab = 90.