most recent 30 from http://mathoverflow.net 2013-05-26T05:33:56Z http://mathoverflow.net/feeds/question/24288 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24288/sufficient-conditions-for-graph-non-isomorphisms Adam J 2010-05-11T20:20:10Z 2010-05-12T01:29:07Z

<p>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)? </p>

http://mathoverflow.net/questions/24288/sufficient-conditions-for-graph-non-isomorphisms/24298#24298 Pete L. Clark 2010-05-11T21:45:09Z 2010-05-11T23:35:23Z

<p>[This is an easy question, but let's be sure to leave an actual answer.]</p> <p>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. </p> <p>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. </p> <p>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 <em>intrinsic</em> 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).</p> <p>An example of a non-instrinsic property: the edges of the graph are bridges in the city of Konigsberg. The first graphic in <a href="http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg" rel="nofollow">http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg</a> 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. </p>

http://mathoverflow.net/questions/24288/sufficient-conditions-for-graph-non-isomorphisms/24316#24316 Glen M Wilson 2010-05-12T01:29:07Z 2010-05-12T01:29:07Z

<p>[Sorry to nitpick, but perhaps it will be helpful to Adam. And I also couldn't comment on Pete's answer, so sorry again!]</p> <p>"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.</p>