Results 1 to 3 of 3

Math Help - HELP with bipartites

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    14

    HELP with bipartites

    For
    n 1, let Pn be the graph with vertex set Vn = {1,2,....,n} and two vertices are adjacent if and only if their sum is a prime number. Show that Pn is bipartite for all n 2.

    Can anyone please get me started with this?

    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


    For n 1, let Pn be the graph with vertex set Vn = {1,2,....,n} and two vertices are adjacent if and only if their sum is a prime number. Show that Pn is bipartite for all n 2.


    Can anyone please get me started with this?
    rule # 1 in problem solving: solve the problem for special cases whenever is possible or, in problems like yours, for small values of n, to get an idea how to do the general case:

    let O and E be the set of odd and even numbers in V_n respectively. clearly O \cup E =V_n and O \cap E = \emptyset. also neither of vertices in O or E are adjacent because sum of any two elements of O

    or E is an even number \geq 4 and thus it cannot be a prime number. Q.E.D.
    Follow Math Help Forum on Facebook and Google+

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

Similar Math Help Forum Discussions

  1. Help with Isomorphic and Bipartites
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 20th 2009, 12:50 PM

Search Tags


/mathhelpforum @mathhelpforum