- #1
cxc001
- 16
- 0
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?
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?