Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph theory and simple circuit help

  1. Nov 24, 2006 #1
    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.
     
  2. jcsd
  3. Nov 24, 2006 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Er, are you talking about graph theory?

    What is the definition of

    C is a simple circuit of length k?​

    So what happens to C if you apply an isomorphism?
     
  4. Nov 24, 2006 #3
    Yes, it is graph theory.
    A simple circuit is a path starting to a point and end to the same point, passing through each edge once.
    I really dont have any idea!
     
  5. Nov 24, 2006 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Okay, what is a path? We need to get to a formal statement, so that we can start proving things... so I'll cut to the chase. Using your definition of circuit (something feels slightly off, but I think it's minor, and I'll let you worry about it), a circuit of length k is:

    (1) An alternating sequence of vertices and edges:
    vertex_0, edge_1, vertex_1, edge_2, ..., edge_k, vertex_k

    (2) The i-th edge is an edge between the (i-1)-th vertex and the i-th vertex.

    (3) Every edge in your graph occurs exactly once in the sequence of edges.

    (4) vertex_0 = vertex_k


    So, can you write down a formal statement of what you're trying to prove?
     
  6. Nov 25, 2006 #5
    MMMM!!
    Not sure
    What do you want me to understand is that 2 graphs are isomorphic if they both have a simple circuit of same length ( besides same # of vertices, edges and degree for vertices)??
    Not sure Perhaps I an tired!
     
  7. Nov 25, 2006 #6

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Nope; that's backwards.

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

    This wants you to show that if two graphs are isomorphic, then one has such a circuit iff the other does.
     
  8. Nov 25, 2006 #7
    Man! I still dont find it.
    Please, I need more help with this problem.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook