How to prove that the number of edges in a simple bipartite graph with n vertices is at most n^2/4?(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Graph Theory - bipartite related proof

**Physics Forums | Science Articles, Homework Help, Discussion**