Results 1 to 3 of 3

Math Help - Graph isomorphism...example help please

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    Graph isomorphism...example help please

    Is there a graph with exactly 3 components, exactly 2 of them not isomorphic? If so, give the example. If not, explain.

    Please help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,712
    Thanks
    1642
    Awards
    1
    Quote Originally Posted by zhupolongjoe View Post
    Is there a graph with exactly 3 components, exactly 2 of them not isomorphic? If so, give the example. If not, explain.
    Think about it a moment. \binom{3}{2}=3.
    So there are 3 distinct pairs.
    Can exactly two components be non-isomorphic?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    296
    Hmm...No it is not. Because if A and B are the exactly two non-isomorphic graphs, then C must be isomorphic to something, but if it is isomorphic to A, there is only one nonisomorphic component. A contradiction.

    Is it that simple?
    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. Difficult problem for isomorphism in graph
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 3rd 2009, 11: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