For a graph $G = (V,E)$ and an element $v \in V, G\backslash v$ denotes the subgraph of $G$ induced by $V\backslash v.$ Find, with proof, an example of a graph $G = (V,E)$ and two vertices $v, w \in V$ with the following properties:
- the subgraphs $G\backslash v$ and $G\backslash w$ are isomorphic but
- there is no automorphism $f$ on $G$ so that $f(v) = w.$
I'm not sure how to find this graph. I think it's relatively easy to find a graph $G$ and two vertices $v$ and $w$ so that $G\backslash v$ and $G\backslash w$ are isomorphic (the cycle $C_4$ and any two distinct vertices should suffice). For the cycle $C_4,$ one could just choose two vertices $v$ and $w$ diagonal from each other and define an automorphism that maps $v$ to $w$ and $w$ to $v$ and the other two vertices to themselves, so the cycle $C_4$ clearly doesn't satisfy the constraints. I'm not sure how to find a graph so that there is no automorphism (isomorphism from a graph to itself) $f$ on $G$ so that $f(v) = w.$ I think it might be useful to show that no such automorphism exists using some sort of contradiction involving two vertices $v$ and $w$ being adjacent in $G$ but $f(v)$ and $f(w)$ not being adjacent.