If two vertices induce isomorphic subgraphs when they are removed, are they conjugate?

Question

This feels like a very natural question, but I am struggling to find a reference. Consider a simple graph $G$, and say two vertices are conjugate if there exists an automorphism of $G$ that switches them. It is not hard to show that if $v,w$ are conjugate than the induced subgraphs on $G\setminus v$ and $G\setminus w$ are isomorphic.

But is the converse true?

More generally, suppose I have a symmetric square matrix $M$. For each index $i$, I will denote $M_i$ to be the square matrix $M$ with row and column $i$ deleted. If for some indices $i,j$, $M_i$ is a permutation of $M_j$, does it follow that there exists a permutation of the indices of $M$ that fixes $M$ but swaps $i$ and $j$?

Answer 1

Here is a counterexample (the skeleton graph of the "pistol" hexiamond, according to the naming from Iamond Ring; MathWorld also calls it the "signpost" hexiamond):

      1
     / \
    /   \
   2-----3-----4
  / \   / \   /
 /   \ /   \ /
5-----6-----7
 \   /
  \ /
   8

If $G$ is the graph above, then $G-4$ and $G-8$ are isomorphic: they are both the skeleton graph of the same pentiamond (which Iamond Ring calls a "funnel"). However, $G$ has no nontrivial automorphisms - in particular, not one that swaps vertices $4$ and $8$. (We can distinguish vertex $7$ in $G$ as the only degree-$3$ vertex adjacent to both degree-$5$ vertices, and then distinguish vertex $4$ from $8$ as the only degree-$2$ vertex adjacent to vertex $7$.)

There are probably many other examples; the way I found this one was by searching Mathematica's GraphData[] collection for graphs with no nontrivial automorphisms, then testing every graph $G$ I found for having a pair of vertices $\{v,w\}$ such that $G-v$ is isomorphic to $G-w$.

Answer 2

The smallest counterexample is the graph $G$ with $8$ vertices $v_1,\dots,v_8$ and $9$ edges $v_1v_2,v_2v_3,v_3v_4,v_4v_5,v_5v_6,v_6v_7,v_7v_8,v_1v_3,v_4v_6$; the vertices $v_3$ and $v_6$ are not conjugate (the only nontrivial automorphism of $G$ just swaps $v_1$ and $v_2$), but $G-v_3\cong G-v_6$. See Fig. 14.9 on p. 141 of Graph Theory by Frank Harary, or F. Harary and E. M. Palmer, On similar points of a graph, J. Math. Mech. 15 (1966), 623–630.

Answer 3

I wonder if I'm missing something, because if the vertices don't have the same degree, then obviously they aren't conjugate. But the graph that is induced by removing a vertex is not affected by the degree of that vertex. So all you have to do is find some graph with conjugate vertices, and add an edge from one of those vertices to another vertex.