Vertex-transitive, finite case

Question

Let $G$ be a graph all of whose vertex-deleted subgraphs are isomorphic. Show that $G$ is vertex-transitive.

I've already seen a proof on this page, but it wasn't complete. Could you please help me?

Answer 1

I think this fill in all the holes. They aren't very deep.

Suppose $G$ has $m$ edges. Since $G\setminus u$ is isomorphic to $G\setminus v$, they have the same number of edges, and $G\setminus u$ has $m-\deg_G(u)$ edges, and $G\setminus v$ has $m-\deg_G(v)$ edges. Thus $G$ is regular, as claimed.

Say $G$ is $k$-regular. Let $f$ be an isomorphism from $G\setminus u$ to $G\setminus v$. Since the neighbors of $u$ in $G$ are of degree $k-1$ in $G\setminus u$, $f$ must map them to the neighbors of $v$ in $g$. Now define a map $g$ from $G$ to $G$ by $$g(x)=\cases{f(x),&$x\ne u$\\v,&$x=u$}$$

We must show that $x,y$ are adjacent in $G$ if and only if $g(x),g(y)$ are adjacent in $G$. If neither $x$ nor $y$ is $u$, then this is true because $g$ extends $f$. If $x$ or $y$ equals $u$, then this follows from the remark that $f$ maps neighbors of $u$ to neighbors of $v$.

For the reverse implication, apply the same argument to $g^{-1}.$