# Graph Theory - bipartite related proof

How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4?

Definition of bipartite graph: a graph whose vertex-set can be partitioned into two subsets such that every edge has one endpoint in one part and one endpoint in the other part.

I try to use induction to prove this problem.

Let n: represents the total # of vertices in a simple bipartite graph (n in positive integer)
Let P(n) = [n^2/4]: represents the max # of edges a simple bipartite graph can have in positive integer

Proof:

Test
n = 0, P(n) = [0^2/4] = 0 (null vertex is trivial)
n = 1, P(n) = [1^2/4] = 0 (I don’t think 1 vertex can have a simple bipartite graph)
n = 2, P(n) = [2^2/4] = 1 ok
n = 3, P(n) = [3^2/4] = 2 ok
n = 4, P(n) = [4^2/4] = 4 ok

So let n>=4
Assume that P(n-1) = [(n-1)^2/4] is true for all n >=4
Prove that P(n) = [n^2/4] is true

How to prove P(n) = [n^2/4] is true?

## Answers and Replies

Induction seems like it would run into the problem of depending on how you have partitioned the nodes of the previous graph (with n-1 nodes) into two halves. Here is possibly an alternate approach. Suppose your graph has n vertices total; if it is bipartite, there is a way to partition the vertices into two sets, V1 with x vertices and V2 with n-x vertices. See if you can find how many possible edges can result as a function of x.

Okay, so by looking at my original assumption P(n-1)=[(n-1)^2/4]=[(n^2-2n+1)/4]=[n^2/4+(1-2n)/4]

So now I need to prove that by adding additional one vertex in result of adding additional (2n-1)/4 edges for all n>5.

So P(n)=P(n-1)+(2n-1)/4= [n^2/4+(1-2n)/4+(2n-1)/4]=[n^2/4]

But how to prove by adding additional one vertex would result in additional (2n-1)/4 edges added though?

epenguin
Homework Helper
Gold Member
From your definition if follows that if the number of vertices in one part is m, then the number in the other part is ?

Then the maximal number of edges is ??

It is very simple algebra that this $$\leq n^2/4$$.

Simple if I am not mistaken - I don't say the most insightful.

Last edited:
epenguin
Homework Helper
Gold Member
Maybe more insightful is to ask what happens to the maximum number of edges if you move a vertex from the minority set to the majority set?

Then think conjecture - you don't need to prove it by itself - that, as usual, the extremal - here maximal - situation is the most symmetric situation. If you have an equal number of vertices in each set, n/2 in each, that is a maximum of n2/4 edges in your bipartite graph for that arrangement. Apply the above argument. Work it out for an odd number of vertices.

Last edited: