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)?
8
-
$\begingroup$ 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? $\endgroup$– Adam JMay 11, 2010 at 20:27
-
2$\begingroup$ 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? $\endgroup$– Benoît KloecknerMay 11, 2010 at 20:28
-
2$\begingroup$ It is sufficient, but not necessary. For example, non-isomorphic trees. $\endgroup$– Tony HuynhMay 11, 2010 at 20:31
-
$\begingroup$ 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. $\endgroup$– user4977May 11, 2010 at 20:35
-
1$\begingroup$ 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. $\endgroup$– Joel David HamkinsMay 11, 2010 at 20:41
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
3
[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.
answered May 11, 2010 at 21:45
-
$\begingroup$ This answer seems a bit circular to me. Aren't intrinsic graph properties precisely those that are preserved under isomorphism? $\endgroup$ May 12, 2010 at 3:03
-
$\begingroup$ 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. $\endgroup$ May 12, 2010 at 3:52
-
$\begingroup$ 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. $\endgroup$ May 12, 2010 at 4:38