Results 1 to 3 of 3

Thread: 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 $\displaystyle n,$ to get an idea how to do the general case:

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

    or $\displaystyle E$ is an even number $\displaystyle \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, 11:50 AM

Search Tags


/mathhelpforum @mathhelpforum