Results 1 to 4 of 4

Math Help - Difficult problem for isomorphism in graph

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    3

    Difficult problem for isomorphism in graph

    Let G10 be a simple graph of 10 vertices, and G10' its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in G10' if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to G10'.

    Please help!!!! (G10 means G with a subscript of 10)
    Last edited by ilovebillu; November 3rd 2009 at 10:15 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,788
    Thanks
    1683
    Awards
    1
    Quote Originally Posted by ilovebillu View Post
    Let 10G be a simple graph of 10 vertices, and 10G its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in 10G if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to 10G.
    Please reread this post. You have used 10G to name two different graphs have you not?
    Did you perhaps mean 10C for the complement?
    Please edit the post to make corrections.
    Or explain what is meant.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    3
    Ooops... sorry..yeah did the corrections
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,788
    Thanks
    1683
    Awards
    1
    Here is a big hint.
    The union of a graph and its complement is a complete graph.
    A complete graph of order ten has forty-five edges.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Isomorphism Problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 14th 2011, 08:02 AM
  2. Replies: 4
    Last Post: February 14th 2010, 03:05 AM
  3. Graph isomorphism...example help please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2009, 08:14 AM
  4. Isomorphism Proof - Graph Theory
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 5th 2008, 02:42 PM
  5. Graph and isomorphism
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2006, 01:34 PM

Search Tags


/mathhelpforum @mathhelpforum