Printable View
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.
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