Two graphs that are not isomorphic?

896 Views Asked by At

They have the same number of vertices and edges. The degree sequences are the same (5,4,4,4,4,4,3). Looking at each vertex of degree i, they have edges to vertices of the same degrees in each graph. I've tried looking for cycles which are not repeated, but there is not a realistic way to do this systematically.

Note that this is from a practice midterm for an introductory combinatorics course, so it should be doable by hand.

two graph images

2

There are 2 best solutions below

1
On BEST ANSWER

In one graph, the single degree-3 node is part of a only one triangle; in the other, two.


The operative heuristics here was to look for pairs of nodes that obviously must map to each other under any isomorphism (in this case the unique nodes of degree 3), and then check whether their immediate neighborhoods look alike.

0
On

By unique vertex degrees we'd have to identify $B$ with $V$ and $D$ with $U$. Then also $G$ would have to be identified with $W$, as these are the only vertices that form triangles respectively with $BD$ and $VU$.

Now I notice that in addition to the triangle $BDG$, there are two more with the edge $DG$, namely $ADG$ and $FDG$.

However in the other graph, corresponding edge $UW$ has only triangles $VUW$ and $XUW$.