1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Graph theory and simple circuit help
  1. Graph Theory (Replies: 4)

Loading...