You are not logged in.
Pages: 1
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 dont 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?
Offline
Hi cxc001
If you want to use induction, here's how I would go about it.
First I would construct a simple bipartite graph with n vertices and [n^2/4] edges, for each n.
You should be able to see how to do this by looking at the small cases. In the case n=1, the graph with one vertex and no edges is a simple bipartite graph.
This shows that P(n) >= [n^2/4].
Then I would show by induction that P(n) <= [n^2/4].
You've already done some base cases.
Suppose that n >=4 and that G is a simple bipartite graph with n vertices.
First show that G has a vertex with degree at most [n/2].
Then show that [(n-1)^2/4] + [n/2] <= [n^2/4]. This part is a little delicate. You may find it easier to split into two parts depending on whether n is even or odd.
Offline
Pages: 1