We say that two vertices $u,v \in V$ in a graph $G=(V,E)$ are similar if there is a graph automorphism $\sigma \in Aut(G)$, s.t. $\sigma(u)=v$.
Is there a graph $G$ with $u,v \in V$ not similar, so that $G-u$ is isomorphic to $G-v$? Here, $G-a$ is the resulting graph after throwing out the vertex $a\in V$ and all the edges $e \in E$ with $a \in e$.
According to the exercise there should be one, but right now I feel closer to disproving it than to prove it. If there is one, could you give me a hint (maybe on the number of vertices, or so)
The terminology I have heard is u and v are in the same "orbit" under the automorphism.
Anyway, there is an example in this paper:
"Automorphism groups of a graphand a vertex-deleted subgraph" Hartkee et al The Electronic Journal Of Combinatorics V7 (2010)
but it's a little large, so I searched through all the simple graphs on eight vertices, and found this smallest one:
It looks like there are 17 other examples in the eights.