Results 1 to 3 of 3

Math Help - Isomorphism Proof - Graph Theory

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    1

    Isomorphism Proof - Graph Theory

    Hi

    If there are two graphs, how would I go about proving that they are isomorphic. Also, how would I go about proving that two other graphs are not isomorphic. Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by undefined911 View Post
    Also, how would I go about proving that two other graphs are not isomorphic. Thanks!
    Find one property one graph has and the other does not.
    Like one graph has all vertex of degrees <=2 but the other has one vertex of degree 3, for example.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    There are several free ‘graph theory programs’ available on the web.
    Several of these the capacity to compare two graphs for an isomorphic relation. Basically they are programmed to compare the two adjacency matrices to see if one matrix can be transform by elementary operations into the other matrix. (That programming if beyond me of course.)

    There is a simple way to see that two graphs are not isomorphic: If they have different degree sequences. Now they can have the same degree sequence and still not be isomorphic. That is, it is necessary that two graphs have the same degree sequence in order to be isomorphic, but it is not sufficient
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 20th 2010, 02:27 AM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 11th 2010, 11:00 PM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 5th 2010, 08:34 AM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 12:00 PM
  5. Graph Theory Proof Help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 4th 2009, 02:52 PM

Search Tags


/mathhelpforum @mathhelpforum