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.


1 Answer 1


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. [email protected]


You must log in to answer this question.

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