15
$\begingroup$

In my class they gave me some necessary conditions for two graphs to be isomorphic, these two graphs satisfy all of them but I don't think they're isomorphic:

Degree sequences are equal.

Same amount of vertices/edges.

$G$ is bipartite $\iff H$ is bipartite.

Is there any methodical (quick) way to solve these kind of questions?

enter image description here

$\endgroup$
23
$\begingroup$

Look at the four vertices of degree $3$ in each graph: in $G$ each of them is adjacent to two of the others, while in $H$ each of them is adjacent to only one of the others. Alternatively, in $G$ they form a $4$-cycle, while in $H$ they do not.

Yet another approach: if you remove them from $G$, what’s left is this graph, with two components.

      *----*  

      *----*

If you remove them from $H$, what’s left is a graph with $4$ vertices and no edges, one with $4$ components.

$\endgroup$
  • $\begingroup$ Thank you very much! I understand your method of deleting all the vertices with degree $n$, if I generalize this, does it hold that $G \simeq H \iff G-\{\text{vertices of degree n}\} \simeq H-\{\text{vertices of degree n}\}$? $\endgroup$ – YoTengoUnLCD Aug 12 '15 at 22:20
  • 3
    $\begingroup$ @YoTengoUnLCD Your generalisation is false, only the implication from the left to the right side is correct. To see this, just consider the graphs with 3 resp. 4 vertices in which every vertex has degree 2. It's probably possible to construct an example in which the graphs have the same number of vertices and edges, but ad hoc I couldn't think of one. $\endgroup$ – Dominik Aug 12 '15 at 22:31
  • 1
    $\begingroup$ @YoTengoUnLCD: Oops: I didn’t notice that you had the implication going both ways. Dominik is entirely correct: it goes only from left to right (which is the direction whose proof I suggested). $\endgroup$ – Brian M. Scott Aug 12 '15 at 22:33
  • 3
    $\begingroup$ A curious psychological phenomenon: When I first looked at this question, my immediate reaction was to look at the subgraph induced by the vertices of degree 3, just as you and two of the three other answerers (so far) did. Only afterward did I notice (as you also did but the others didn't) that it's easier to look at the subgraph induced by the vertices of degree 2. I can't think of any good reason why we all jumped at the degree 3 picture initially. $\endgroup$ – Andreas Blass Aug 12 '15 at 23:54
  • 1
    $\begingroup$ @AndreasBlass, I added a degree-2 based answer at the same time you were writing the comment. Not the induced subgraph but to assess Hamiltonicity. $\endgroup$ – ASCII Advocate Aug 13 '15 at 1:28
11
$\begingroup$

In general, this problem is known as graph isomorphism problem and is very hard to solve.

In this special case it can be proven relatively easy. The left graph has a path consisting of 3 distinct vertices of degree 3, but the right graph does not have this property.

$\endgroup$
5
$\begingroup$

Yet another difference: In G, you can remove a pair of adjacent vertices to disconnect the graph. The graph H does not have this property, though.

Remember the old joke about, "How do I get to Carnegie Hall?" "Practice, practice, practice!" ? The same thing applies here. You look for a property that one graph has that the other one doesn't, and the more properties you know, and the more practice you get, the easier it becomes.

$\endgroup$
4
$\begingroup$

As suggested in other answers, in general to try to show two graphs are NOT isomorphic it suffices to find some invariant conditions, e.g. in terms of counts of vertices of various degrees and counts of their neighbors of various degrees and counts of paths through vertices of different degrees, etc. To show two graphs ARE isomorphic there is basically no known fast method, but you can limit your search for the right isomorphism by using the restrictions outlined above.

In the case of your two graphs, here are examples of how to see they are not isomorphic (similar to other answers). One way is to count the number of vertices of degree 3 that have 2 neighbors also of degree 3. In your first graph the answer is 4, and in the second graph the answer is 0. You can also count how many simple paths there are of length 3 that pass through only degree 3 nodes. In the first graph you can find one, but in the second graph you can't.

$\endgroup$
2
$\begingroup$

$G$ is Hamiltonian (has a cycle using every vertex once) and $H$ is not.

To see the second point, $H$ has several vertices of degree $2$. Any Hamilton cycle must use all the edges on these vertices. But those edges form a pair of $4$-cycles, and cannot be part of a cycle on all the vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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