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