Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Consider the following graph property: for each $u, v \in V(G)$, we have that $G - u \cong G-v$. This property implies a high "symmetry" of the graph.
We can easily see that every vertex-transitive graph has this property. My question: is the converse true?
I've tried to create a counterexample but so far I haven't found any. I appreciate any answer, guidance or reference. Thanks in advance!
In the finite case,the converse is true. The trick is to note that all the subgraphs $G\setminus u$ are isomorphic, then $G$ must be regular, say with valency $k$. Hence the neighbours of $u$ in $G$ are precisely the vertices of degree $k-1$ in $G\setminus u$. It follows that any isomorphism from $G\setminus u$ to $G\setminus v$ must map the vertices of $G\setminus u$ adjacent to $u$ (in $G$) to the vertices of $G\setminus v$ adjacent to $v$b (in $G$). Given this, it is not hard to show that each isomorphism from $G\setminus u$ to $G\setminus v$ extends to an automorphism of $G$ that maps $u$ to $v$.
Edit: Carsten Thomassen (JCT B, vol 43) proved that a locally-finite vertex-transitive graph with no isolated vertices is vertex-transitive if and only if its vertex-deleted subgraphs are all isomorphic.
Partial answer:
I found an infinite, but countable counterexample. Imagine a disjoint sum of countably infinitely many copies of $K_1$ and $K_2$, that is, $$\biguplus_{n \in \mathbb{N}}(K_1 \uplus K_2).$$
Then, if you remove any vertex, the graph is still isomorphic to itself ($K_2$ becomes $K_1$, while $K_1$ just disappears). Yet, there is no automorphism that connects vertices belonging to $K_1$ and $K_2$.
I hope this helps $\ddot\smile$
