1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory - bipartite related proof

  1. Sep 15, 2010 #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


    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?
  2. jcsd
  3. Sep 15, 2010 #2
    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.
  4. Sep 15, 2010 #3
    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?
  5. Sep 15, 2010 #4


    User Avatar
    Homework Helper
    Gold Member

    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.
    Last edited: Sep 16, 2010
  6. Sep 16, 2010 #5


    User Avatar
    Homework Helper
    Gold Member

    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 n2/4 edges in your bipartite graph for that arrangement. Apply the above argument. Work it out for an odd number of vertices.
    Last edited: Sep 16, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook