3
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great, thanks you! $\endgroup$ – P-L Mar 3 '16 at 2:38
1
$\begingroup$

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$.

$\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.