Vertices $u$ and $v$ in a graph $X$ are similar if there is an automorphism of $X$ that maps $u$ to $v$. If $u$ and $v$ are similar, then the vertex-deleted subgraphs $X\diff u$ and $X\diff v$ are isomorphic. If $X\diff u$ and $X\diff v$ are isomorphic but $u$ and $v$ are not similar, we say that they are pseudosimilar. It is not obvious that pairs of pseudosimilar vertices exist, but we will see that they do.

C9 = graphs.CycleGraph(9); C9

Cycle graph: Graph on 9 vertices

The vertex set of $C9$ is $\{0,\ldots,8\}$. We want to add three new vertices to $C9$, adjacent to $1$, $4$ and $7$ in turn and delete the vertex $0$.

D = C9.copy()
D.add_edges([(1,9), (4,10), (7,11)])
D.delete_vertex(0)

Here's $D$:

The automorphism group of $D$ has order 2:

D.automorphism_group().order()

2

and we can determine its orbits:

D.automorphism_group(return_group=False, orbits=True)

[[1], [2], [3], [4], [5], [6], [7], [8, 11], [9], [10]]

As an alternative to the last command we could try the following, but its output is misleading!

D.automorphism_group().orbits()

[[1], [2], [3], [4], [5], [6], [7, 10], [8], [9], [11]]

This is because automorphism groups of graphs do not always exactly match the integer symbols for the permutation group to the names of the vertices. Here is the translation between vertex names to permutation group symbols, as a Python dictionary.

D.automorphism_group(return_group=False, translation=True)

{1: 11, 2: 1, 3: 2, 4: 3, 5: 4, 6: 5, 7: 6, 8: 7, 9: 8, 10: 9, 11: 10}

I claim $D$ has a pair of pseudosimilar vertices. In this case we could find them by inspecting our drawing of $D$, but we work through a general approach. The idea is to find a canonical label for each of the 11 vertex-deleted subgraphs of $D$. The sage command

E = D.canonical_label()
E.edges(labels=False)

[(0, 10), (1, 10), (2, 8), (3, 9), (4, 6), 
(4, 10), (5, 7), (5, 8), (6, 9), (7, 9)]

returns a canonized form of $D$. So graphs $G$ and $H$ are isomorphic if and only if their canonized forms are equal. For example

P = graphs.PetersenGraph()
Q = graphs.CompleteGraph(5).line_graph().complement()
Pc = P.canonical_label(); Qc = Q.canonical_label()
P == Q, Pc == Qc

(False, True)

The only problem left is that the return value of canonical_label() is not hashable. We can circumvent this as follows.

The following procedure constructs a hashable canonical label for $G\diff i$, given $G$ and $i$.

def vdi(G, i):
    H = G.copy()
    H.delete_vertex(i)
    return (H.canonical_label().graph6_string(), i)

We can now construct our list of pairs of the form (string, vertex):

orbs = D.automorphism_group( return_group=False, orbits=True)
orb_reps = [it[0] for it in orbs]
labels = [vdi(D,i) for i in orb_reps]
labels

[('I??G?DaDO', 1), ('I_???CpB_', 2), ('I??X??BoO', 3), 
('I???GOPW_', 4), ('I??G_GBw?', 5), ('I??X??BoO', 6), 
('I???Gg_Ag', 7), ('I??OQaGH_', 8), ('I???oH`b?', 9), 
('I?COOIAWO', 10)]

and on inspecting the output, we see that $D\diff 3\cong D\diff 6$.

As an exercise, construct a graph on 8 vertices with a pair of pseudosimilar vertices.

Now we describe how to get a list of the sets of vertices such that all vertices in the same set have the same vertex-deleted subgraphs. First we need to convert our list of pairs to a dictionary keyed on the first term of the pair; the value of a key will be all second terms with the same first term. (The keys for a dictionary must be hashable, so this is why we needed the graph6 strings.)

def ls_dict( tuples):
    dc = {} 
    for pair in tuples:
        if dc.has_key( pair[0]):
            dc[ pair[0]].append(pair[1])
        else:
            dc[ pair[0]] = [pair[1]]
    return dc

Now if dc is a dictionary whose values are lists, we compute a list consisting of those values whose length is at least $k$:

def get_families( dc, k):
    families = []
    for str, vxs in dc.iteritems():
        if len(vxs) >= k:
            families.append( vxs)
    return families

We apply this to our list labels:

get_families( ls_dict( labels), 2)

[[3, 6]]

We see again that 3 and 6 form a pseudosimilar pair of vertices.

For further reading on pseudosimilar vertices, you will have to dig out papers on the topic. I suspect that few of these are on the web, since they predate LaTeX. Fortunately we still have libraries. Note that pseudosimilar sets of size greater than two are possible.