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!


2 Answers 2


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, 2014 at 23:05
  • $\begingroup$ @dtldarek , or anyone, this made me wonder: Is there an analogous theorem for finite edge-transitive graphs? Something like: For any edge $e$ and $f$, $G-e$ is isomorphic to $G-f$? $\endgroup$ May 8, 2021 at 3:19

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$ Dec 12, 2014 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .