Does $G\!-\!v_1 \simeq G\!-\!v_2$ mean an automorphism of $G$ maps $v_1$ to $v_2$?

76 Views Asked by At

For a simple undirected graph $G$, suppose we have two vertices $v_1$ and $v_2$ such that $G-v_1 \simeq G-v_2$. Does this necessarily mean that there is an automorphism of $G$ that maps $v_1$ to $v_2$?

This is just a condition that I've assumed to be true for awhile now without thinking too hard about whether or not it's actually true. Using the condition that $G-v_1 \simeq G-v_2$ has been a useful way to characterize two vertices as being "the same," but I was wondering if this actually corresponds to automorphisms of the graph.

2

There are 2 best solutions below

3
On BEST ANSWER

No. This graph is a counterexample:

graph here

2
On

Another counterexample, with the black vertices as $v_1$ and $v_2$. This graph has trivial automorphism group.

counterexample