Results 1 to 3 of 3

Math Help - Bipartite Simple Graph

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    14

    Bipartite Simple Graph

    Can anyone please help me with this question? How can i start it?


    Show that if G is a bipartite simple graph with v vertices and e edges, then e v/4
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by sanorita_belle View Post

    Can anyone please help me with this question? How can i start it?


    Show that if G is a bipartite simple graph with v vertices and e edges, then e v/4
    let V be the set of vertices. then V=A \cup B, where A \cap B= \emptyset, \ |A|=m, \ |B|=n. clearly v=m+n and e \leq mn. we also have mn \leq \frac{(m+n)^2}{4} because (m-n)^2 \geq 0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    14
    Thanks alot
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. complete bipartite subgraph of a graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 6th 2011, 05:13 PM
  3. Bipartite graph proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 2nd 2010, 11:47 AM
  4. Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 02:37 AM
  5. Bipartite graph problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 11th 2008, 10:54 PM

Search Tags


/mathhelpforum @mathhelpforum