graph theorygraph-isomorphism
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?
The graph at left has a 3-cycle $(a,b,j)$ (also $(f,e,g)$). The graph at right has none. They are not isomorphic.
It may be worth noting that the graph at right is simply (the skeleton of) a pentagonal prism; consequently, each vertex is (in an appropriate sense) "equivalent" to every other vertex. This is not the case in the graph at left.
Also, the graph at right, as illustrated, is planar; no edges intersect. In the graph at left, you can replace "chords" $bj$ and $eg$ with paths that travel "outside the circle", eliminating intersections with $af$, but you can't do that with both of $ch$ and $di$ and not have $ch$ and $di$ cross; an edge intersection is inevitable (although this needs rigorous proof), so the graph is non-planar.
Once you know, as pointed out in this answer, that $$f(A)=7,\: f(B)=4,\: f(C)=3,\: f(D)=6,\: f(E)=5,\: f(F)=2,\: f(G)=1$$ isomorphism, you can create an animation illustrating how to morph one graph into the other. Let's say that ${vc}_1$ is a list of vertex coordinates for one and ${vc}_2$ is the corresponding list of vertex coordinates for the other. (It's important that the order of the vertex coordinates be dictated by the isomorphism.) We can then morph from one graph to the other using a function like
$$p(t) = t \, {vc}_2 + (1-t) {vc}_1.$$
Here's the result:
Since several folks asked for code generating the animation in the comments, you can find it here:
Best Answer
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.