Isomorphism in regular graphs

268 Views Asked by At

Let $G$ be a connected regular graph. Consider two different vertices $u,v$ of $G$. Let $H_1$ be the graph obtained from $G$ by deleting vertex $u$, and $H_2$ be the graph obtained from $G$ by deleting vertex $v$. Is it necessary that $H_1$ and $H_2$ are isomorphic?

1

There are 1 best solutions below

3
On

No, they're not necessarily isomorphic. For easy counterexamples look at the disjoint union of two different regular graphs of the same degree (e.g. different cyclic graphs), then delete a point from each of the graphs.