Graph Theory - bipartite related proof

[cxc001]

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?

 

[Tedjn]

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.

 

[cxc001]

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]

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 [tex] \leq n^2/4 [/tex].

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

 

[epenguin]

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 n²/4 edges in your bipartite graph for that arrangement. Apply the above argument. Work it out for an odd number of vertices.