8
$\begingroup$

Prove that for a bipartite graph $G$ on $n$ vertices the number of edges in $G$ is at most $\frac{n^2}{4}$.

I used induction on $n$.

Induction hypothesis: Suppose for a bipartite graph with less than $n$ vertices the result holds true.

Now take a bipartite graph on $n$ vertices.Let $x,y$ be two vertices in $G$ where an edge exist between $x$ and $y$. Now remove these two vertices from $G$ and consider this graph $G'$. $G'$ has at most ${(n-2)^2}\over4$. Add these two vertices back. Then the number of edges $G$ can have is at most

$$|E(G')|+d(x)+d(y)-1$$

My question is in my proof I took $d(x) + d(y) \le n$, where $d(x)$ denotes the degree of vertex $x$. Can I consider $d(x)+d(y) \leq n$? I thought the maximum number of edges is obtained at the situation $K_{\frac n 2,\frac n 2}$

$\endgroup$
  • $\begingroup$ Yes- $\frac{n}{2} \cdot \frac{n}{2} = \frac{n^{2}}{4}$. If $n$ is even, this works out very well. Otherwise, $n$ is odd. So one partition will have an extra vertex. $\endgroup$ – ml0105 Jan 10 '15 at 6:26
  • $\begingroup$ $d(x)+d(y)\leq n$ looks valid. You didn't mention your two base cases to get the induction started. Can you add that? Also a brief nod in the direction of the emptying of one part of G in the case where x or y is the last node in its part. $\endgroup$ – Joffan Jan 10 '15 at 6:35
16
$\begingroup$

There is no need to use induction here. A bipartite graph is divided into two pieces, say of size $p$ and $q$, where $p+q=n$. Then the maximum number of edges is $pq$. Using calculus we can deduce that this product is maximal when $p=q$, in which case it is equal to $n^2/4$.

To show the product is maximal when $p=q$, set $q=n-p$. Then we are trying to maximize $f(p)=p(n-p)$ on $[0,n]$. We have $f'(p)=n-2p$, and this is zero when $p=n/2$. After checking the end points we conclude that the maximum is $n^2/4$ at $p=n/2$.

$\endgroup$
  • $\begingroup$ How can it be shown that product is maximal when p=q $\endgroup$ – sam_rox Jan 10 '15 at 7:06
  • $\begingroup$ @sam_rox please see edit. $\endgroup$ – Matt Samuel Jan 10 '15 at 7:10
  • 1
    $\begingroup$ you can also write $p$ as $\frac{n}{2}-l$ and use the trick at the bottom of my result. $\endgroup$ – Jorge Fernández Hidalgo Jan 10 '15 at 7:20
3
$\begingroup$

The sum of the degrees of vertices $x$ and $y$ is indeed less than or equal to $n$. One reason for this is that if a vertex $v$ is adjacent to $x$ it cannot be adjacent to $y$ since $y$ and $v$ would be in the same part.


I would like to share my proof, please tell me what you think of it: The bipartite graph on $n$ vertices with the most edges is clearly a complete bipartite graph, otherwise we could take that graph, add an edge and we would have a graph with more edges.

In a complete bipartite graph with parts of size $k,n-k$ the vertices in the part with $k$ vertices have order $n-k$ and the vertices in the part with $n-k$ vertices have order $k$. The sum of the degrees is then $2k(n-k)$, so by the handshaking lemma the number of edges is $k(n-k)$

Now write $k$ as $\frac{n}{2}-j$. Then $k(n-k)=(\frac{n}{2}-j)(\frac{n}{2}+j)=\frac{n^2}{4}-l^2\leq \frac{n^2}{4}$

$\endgroup$
0
$\begingroup$

suppose the bipartite graph has m vertices in set1 and n vertices in set2 . the sum of degrees of all vertices would be 2 * e= 2 * m * n thus, e = m * n and m+n = v so n*(v-n)= e solve this quadratic equation and discriminant .

$\endgroup$
0
$\begingroup$

Suppose $p,q$ are nonnegative integers with $p+q=n,$ and that $K_{p,q}$ has the maximum number of edges among all bipartite graphs with $n$ vertices.

If we move one vertex from the side with $p$ vertices to the side with $q$ vertices, we lose $q$ edges and gain $p-1$ new edges. Since the number of edges was already maximized, we must have $p-1\le q,$ that is, $p-q\le1.$ Symmetrically, we also have $q-p\le1,$ and so $|p-q|\le1.$

If $n$ is even, then from $p+q=n$ and $|p-q|\le1$ it follows that $p=q=\frac n2,$ and $pq=\frac{n^2}4=\left\lfloor\frac{n^2}4\right\rfloor.$

If $n$ is odd, then $\{p,q\}=\left\{\frac{n-1}2,\frac{n+1}2\right\},$ and $pq=\frac{n^2-1}4=\left\lfloor\frac{n^2}4\right\rfloor.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.