Results 1 to 2 of 2

Math Help - Graph and isomorphism

  1. #1
    Member
    Joined
    Nov 2005
    Posts
    111

    Graph and isomorphism

    Hi,
    I have this problem I don't understand I have been on it for days now:

    Show that the existence of a simple circuit of length k, where k is a positive integer greater than 2, is an isomorphism invariant.

    please can someone help me with it?
    Thank you
    B.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2005
    Posts
    39
    To say that a certain property P is an "isomorphism invariant" is simply to say that, if structure A has property P, then any structure B which is isomorphic to A will also have property P.

    If you are familiar with any abstract algebra, a good example of an isomorphism invariant is the property of "being abelian" (for groups). If two groups are isomorphic, then they are either both abelian, or both not.

    Firstly, what does it mean for two graphs to be isomorphic? It means that there is a bijection between the vertices which always maps edges onto edges. That is, you have a bijective function f:G --> G' such that two points A and B on the graph G will be connected if and only if the corresponding points f(A), f(B) are also connected.

    So, the thing to show is that if A[1], ..., A[k] is a circuit of length k in the graph G, then f(A[1]), ..., f(A[k]) is a circuit of length k as well in the graph G'. This is clear, since f(A[1]) will be connected to f(A[2]) will be connected to f(A[3]), and so on. Showing that simple circuits map to simple circuits requires a bit more work, but basically the same idea, just follow the definition. Hope that helps, good luck
    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. Graph isomorphism...example help please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2009, 08:14 AM
  5. Isomorphism Proof - Graph Theory
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 5th 2008, 02:42 PM

Search Tags


/mathhelpforum @mathhelpforum