- #1

- 16

- 0

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?