Find an example of two non-isomorphic regular graphs $H_1$ and $H_2$ of same size and order satisfy these two conditions:

  1. for all 2-element subsets $S_1 \subset V(H_1)$ and $S_2 \subset V(H_2)$, the graphs $H_1-S_1$ and $H_2 -S_2$ are not isomorphic; and

  2. there exist 3-element subsets $T_1 \subset V(H-1)$ and $T_2 \subset V(H_2)$ such that $H_1 -T_1$ and $H_2 -T_2$ are isomorphic.

I have checked some pairs of 2-regular and 3-regular graphs of the same size and order, but can't find any examples that satisfy these 2 condition. I wonder if someone can give me a hint.


The answer is straight forward when you let $H_1$ be a cube which has $8$ vertices and it is $3$-regular and let $H_2$ be a $3$-regular graph with $8$ vertices that contains four triangles. Sure, $H_1$ and $H_2$ are not isomorphic.

Meanwhile, to construct $H_2$, two triangles each will share a common base on two sides of $H_2$ while the tops of these inverted triangles will be joined by a bridge each. You will have two bridges. Now if you delete any two edges from the cube and delete the two vertices of $H_2$ that constitutes the bases of the inverted triangles on each side of $H_2$ you will get $H_1-S_1$ and $H_2-S_2$ that non-isomorphic. Now, proceed from the resulting graphs and delete a vertex of degree $3$ in $H_1-S_1$ and any vertex of degree $H_2-S_2$ you will surely get the ultimate graphs $H_1-S_1'$ and $H_2-S_2'$ that are isomorphic. I hope you will find helpful. Sorry for not including the diagrams it is just that I don't know how to draw on this platform.

If you find it confusing you can send me an email for the diagrams. g201302910@kfupm.edu.sa


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.