19
$\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$
0
28
$\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$
9
  • $\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$ 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$ 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$ 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$ Aug 13 '15 at 1:28
12
$\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$
6
$\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$
6
$\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$
3
$\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$
0
$\begingroup$

A vertex cover of a graph is a subset $C$ of the vertices such that at least one vertex of every edge is in $C$. A vertex cover $C$ is minimal if no proper subset of $C$ is a vertex cover. If two graphs are isomorphic then there must be a size-preserving bijection between their sets of minimal vertex covers.

To see that the given graphs are not isomorphic let's label the vertices of the graphs like so:

The graph <span class=$G$ with a vertex labeling" />The graph <span class=$H$ with a vertex labeling" />

There are precisely two minimal vertex covers of $G$ of size four: $\{a,d,e,h\}$ and $\{b,c,f,g\}$. But there are three such covers of $H$: $\{a,d,e,f\}, \{b,c,e,f\}, \{b,c,g,h\}$. So the two graphs can't be isomorphic.

For larger examples computing minimal vertex covers by hand is arduous. Fortunately there is open source software available for quickly compute minimal vertex covers. For example one can use the Macaulay2 package EdgeIdeals to compute all of the minimal vertex covers of both graphs as follows.

i1 : loadPackage "EdgeIdeals";

i2 : S = ZZ/2[a..h]; -- a polynomial ring in 8 variables, one for each vertex

i3 : G = graph (S, {{a, b}, {a, c}, {b, d}, {c, d}, {c, e}, {d, f}, {e, f}, {e, g}, {f, h}, {g, h}});

i4 : H = graph (S, {{a, b}, {a, c}, {b, d}, {b, e}, {c, d}, {c, f}, {e, g}, {e, h}, {f, g}, {f, h}});

i5 : I = coverIdeal G

o5 = monomialIdeal (bcfg, acdfg, adefg, adeh, bcdeh, bcefh)

o5 : MonomialIdeal of S

i6 : J = coverIdeal H

o6 = monomialIdeal (bcef, adef, bcgh, acdegh, abdfgh)

o6 : MonomialIdeal of S

We see from the output in line o5 that $G$ has a total of 6 minimal covers: two of size four and four of size five. On the other hand line o6 shows that $H$ only has five: three of size four and two of size six.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .