Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have two graphs $G_1$ and $G_2$. To check whether these two graphs are not isomorphic, is it sufficient to find a $k$-cycle in $G_1$ but can't find a $k$-cycle in $G_2$ (or vice versa)?

share|improve this question

closed as off topic by Scott Morrison May 12 '10 at 16:34

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
Well what if they are not trees? For example, suppose the two graphs have the same order and size and degree sequence. How would you show that they are not isomorphic? –  Adam J May 11 '10 at 20:27
2  
Nevertheless, the proposed condition is sufficient, although it is not necessary for the graph not to be isomorphic. Anyway, I don't think this question is suitable for MO; Adam J, have you checked the fac? –  Benoît Kloeckner May 11 '10 at 20:28
2  
It is sufficient, but not necessary. For example, non-isomorphic trees. –  Tony Huynh May 11 '10 at 20:31
    
I would like to add, to Adam J, that it seems as though you have a good intuition about the graph isomorphism concept. Before reading the FAQ and asking this question on another site, I would encourage you to make a serious effort to answer your own question rigorously. –  user4977 May 11 '10 at 20:35
1  
More generally, for more information on the graph isomorphism problem, see en.wikipedia.org/wiki/Graph_isomorphism_problem. This problem is interesting in that there is no known polynomial time algorithm, but it is not known to be NP complete. Indeed, it is not NP complete unless the polynomial time hierarchy collapses to its second level. –  Joel David Hamkins May 11 '10 at 20:41

2 Answers 2

[This is an easy question, but let's be sure to leave an actual answer.]

Yes, if $G_1$ and $G_2$ are graphs and there exists a positive integer $k$ such that $G_1$ has a $k$-cycle and $G_2$ does not, then $G_1$ and $G_2$ cannot be isomorphic.

As others have pointed out, although this is a valid and useful tool for showing non-isomorphism of graphs, it is certainly not always applicable: for instance some graphs ("forests") have no cycles of any length.

Let me try to address a more general version of your original question. In order to show that two graphs are not isomorphic [and the same holds for isomorphism of other mathematical structures as well], it suffices to find an intrinsic property that the first possesses and the second lacks. When you meet a new mathematical structure like a graph and are learning about various properties that it may or may not possess, you should ask yourself whether those properties are intrinsic properties. Usually the answer will be "yes". If the answer is "no", you should ask yourself -- or someone else -- why you are studying a non-instrinsic property! Once you acquire the right perspective, it will be easy to avoid non-instrinsic properties when you want to (which is most of the time).

An example of a non-instrinsic property: the edges of the graph are bridges in the city of Konigsberg. The first graphic in http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg shows that this is not an instrinsic property, and of course this is rather the point: by letting go of this inessential feature, Euler began the instrinsic study of graphs, i.e., graph theory.

share|improve this answer
    
This answer seems a bit circular to me. Aren't intrinsic graph properties precisely those that are preserved under isomorphism? –  Tony Huynh May 12 '10 at 3:03
    
Yes, they are, but I don't see why it's circular. You choose the isomorphisms according to what kind of structure you want to preserve. –  Pete L. Clark May 12 '10 at 3:52
    
I see what you are saying. However, in this case I think the OP already has a notion of isomorphism in mind and is trying to get a feel for which properties are intrinsic with respect to the (standard) definition of graph isomorphism. For example, the property of containing a cycle of length k is not an intrinsic property if I consider two graphs G and H to be 'isomorphic' if they are homeomorphic as topological spaces. –  Tony Huynh May 12 '10 at 4:38

[Sorry to nitpick, but perhaps it will be helpful to Adam. And I also couldn't comment on Pete's answer, so sorry again!]

"Intrinsic properties" are always relative to some kind of idea of "sameness" (or something like that). The fact that the edges are bridges in the one picture is not intrinsic with respect to the picture representing a graph. It is indeed an intrinsic property if we were trying to distinguish paintings though. In a more mathematical context, the situation could be something like dealing with the geometry and topology of an object: an ellipsoid and sphere are homeomorphic, but have different geometry. So Gaußian curvature is geometrically intrinsic but not topologically intrinsic.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.