  We provide a mathematically and conceptually robust notion of quantum
superpositions of graphs. We argue that, crucially, quantum superpositions of
graphs require node names for their correct alignment, which we demonstrate
through a no-signalling argument. Nevertheless, node names are a fiducial
construct, serving a similar purpose to the labelling of points through a
choice of coordinates in continuous space. Graph renamings, aka isomorphisms,
are understood as a change of coordinates on the graph and correspond to a
natively discrete analogue of continuous diffeomorphisms. We postulate renaming
invariance as a symmetry principle in discrete topology of similar weight to
diffeomorphism invariance in the continuous. We explain how to impose renaming
invariance at the level of quantum superpositions of graphs, in a way that
still allows us to talk about an observable centred at a specific node.
