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.

  • $\begingroup$ You beat me to it $\ddot\smile$! I've just arrived at identical reasoning, but you were first, good job. $\endgroup$ – dtldarek Dec 12 '14 at 23:05

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$

  • $\begingroup$ I am mainly interesed in the finite and simple case, but this is interesting anyway. Many thanks! $\endgroup$ – David Hackenger Dec 12 '14 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.