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)?
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.
[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.
[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.