Results 1 to 8 of 8

Math Help - Bipartite Graphs

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Bipartite Graphs

    A graph G has a property that every edge of G joins an odd vertex with an even vertex. Prove that G is bipartite and has even size.

    Please help me out.

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    Hi,

    Quote Originally Posted by zhupolongjoe View Post
    A graph G has a property that every edge of G joins an odd vertex with an even vertex. Prove that G is bipartite and has even size.

    Please help me out.

    Thanks.
    this is how i understand your language, pls correct me if otherwise:
    "odd vertex" means vertex of odd degree,
    "size of G" is the number of vertices of G.

    Then the first statement is obvious (partition of the graph consists of the set of odd-degree vertices and the set of even-degree vertices),
    and the second statement is wrong ( consider graph G=(V,E) where V={u,v,w} and E={{u,v},{v,w}} ).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    THat's correct....why the text tell me to prove something that is false?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    125
    Quote Originally Posted by zhupolongjoe View Post
    THat's correct....why the text tell me to prove something that is false?
    I don't know.. provided you typed the problem correctly and definitions fit, we can't say anything about the size of G. In fact, the size of G can be an arbitrary number n: take G=(V,E), V={v_i ; i < n}, E = empty set.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    THat's correct....why the text tell me to prove something that is false?
    In a graph with all even vertices, every odd vertex is joined to an even vertex.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Well okay, verbatim, the problem reads "A graph G has the property that every edge of G joins an odd vertex with an even vertex. Show that G is bipartite and has even size."
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Oh, oops, actually the books uses "size" for number of edges, not vertices. (order is number of vertices)...maybe that will make a difference.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Well okay, verbatim, the problem reads "A graph G has the property that every edge of G joins an odd vertex with an even vertex. Show that G is bipartite and has even size."
    Do you see how important language is?
    Even now I would prefer the addition of the phrase “A graph with at least one edge…”.
    It is clear from the statement of the problem that no edge can have two even vertices or two odd. Therefore, the graph is partition into two sets, even vertices and odd vertices. No two vertices in either set share an edge.
    Therefore, the graph is bipartite.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 23rd 2010, 01:12 AM
  2. Help with proof on bipartite graphs!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 14th 2010, 06:00 PM
  3. Complete Bipartite Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 29th 2010, 12:27 PM
  4. proof for bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 29th 2010, 08:29 AM
  5. SOS - bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 29th 2006, 11:50 PM

Search Tags


/mathhelpforum @mathhelpforum