On the vector space spanned by unlabeled graphs on \(n\) vertices, vertex deletion \(D\) and vertex insertion \(U\) satisfy
$$ \boxed{DU-2UD=2^nI.} $$
This is not a numerical pattern. The proof fits in one paragraph, and after the right inner product is chosen it implies that every vertex-deck operator is surjective.
I did not expect the onto statement to fall out quite this cleanly. The factor of two is the whole trick :)
Deletion and insertion#
Let \(\mathcal G_n\) be the isomorphism classes of simple graphs on \(n\) vertices, and write
$$ V_n=\mathbb Q[\mathcal G_n]. $$
The deck operator deletes one vertex at a time:
$$ D[G]=\sum_{v\in V(G)}[G-v]. $$
Its upward companion takes a graph \(H\), adds a new vertex, and joins it to every possible subset \(S\subseteq V(H)\):
$$ U[H]=\sum_{S\subseteq V(H)}[H+_S v]. $$
These are operators on isomorphism classes, so their matrix entries are multiplicities. If
$$ d(G;H)=\#\{v:G-v\cong H\} $$
and
$$ u(H;G)=\#\{S:H+_Sv\cong G\}, $$
then \(d(G;H)\) and \(u(H;G)\) are usually different. The two integer matrices are not ordinary transposes.
The missing normalization is the automorphism group.
The automorphism weight points in the surprising direction#
Give the graph basis the inner product
$$ \langle G,G'\rangle= \begin{cases} |\operatorname{Aut}(G)|,&G\cong G',\\ 0,&G\not\cong G'. \end{cases} $$
Orbit-stabilizer on pointed graphs \((G,v)\) and attachment pairs \((H,S)\) gives
$$ u(H;G)|\operatorname{Aut}(G)| = d(G;H)|\operatorname{Aut}(H)|. $$
Therefore
$$ \boxed{U=D^*.} $$
The weight is \(|\operatorname{Aut}(G)|\), not its reciprocal. The reciprocal is the species-looking normalization I wanted to write first, and it is wrong already for \(P_3\) and \(K_{1,3}\). I find this inversion ambush extremely endearing.
Why the coefficient is two#
Fix an \(n\)-vertex graph \(G\). In \(D(U(G))\), first add a new vertex with neighborhood \(S\subseteq V(G)\), then delete a vertex.
Deleting the new vertex returns \(G\). There are \(2^n\) choices of \(S\), so this contributes
$$ 2^n[G]. $$
Now delete an old vertex \(w\). Once \(w\) is removed, the two choices
$$ w\in S \qquad\text{and}\qquad w\notin S $$
produce the same subset of \(V(G-w)\). Every insertion after deleting \(w\) therefore appears exactly twice. Summing over \(w\),
$$ DUG=2UDG+2^nG. $$
That is the displayed relation.
It is a \(q\)-commutation law with \(q=2\), rather than an ordinary diagonal commutator. In Fomin's language this is a quantized dual graded graph with a level-dependent constant \(2^n\). The familiar differential-poset machinery does not transfer verbatim because
$$ [D,U]=UD+2^nI $$
is not diagonal.
The norm identity makes the deck onto#
Adjointness turns the operator relation into an exact norm identity. For \(x\in V_n\),
$$ \begin{aligned} \|Ux\|^2 &=\langle DUx,x\rangle\\ &=\langle(2UD+2^nI)x,x\rangle\\ &=2\|Dx\|^2+2^n\|x\|^2. \end{aligned} $$
Hence
$$ \boxed{\|Ux\|^2\ge 2^n\|x\|^2.} $$
So \(U:V_n\to V_{n+1}\) is injective, with
$$ \sigma_{\min}(U_n)\ge 2^{n/2}. $$
In finite dimensions the adjoint of an injective map is surjective. Since \(D=U^*\),
$$ \boxed{D_n:V_n\longrightarrow V_{n-1}\text{ is surjective for every }n.} $$
The verifier checks the relation, adjointness, norm identity, and dimensions in exact arithmetic through all graphs on six vertices. The proof itself is general; the finite run is there so the multiplicities and automorphism normalization can be poked directly.
Onto does not mean reconstructible#
Surjectivity here is a statement about formal rational combinations of graphs. Every vector in \(V_{n-1}\) is the deck of some vector in \(V_n\). It does not say that every multiset is the deck of one actual graph.
It also does not prove reconstruction. Instead it gives the reconstruction problem a very exact place to live:
$$ V_n=\operatorname{im}(U_{n-1})\perp\ker(D_n), $$
with
$$ \dim\ker(D_n)=g_n-g_{n-1}, $$
where \(g_n=|\mathcal G_n|\). For \(n=1,\ldots,6\), these kernel dimensions are
0, 1, 2, 7, 23, 122.
Graph reconstruction at order \(n\) is exactly the assertion that this known orthogonal kernel contains no difference
$$ [G]-[G'] $$
of two nonisomorphic graphs.
So the deck map has maximum possible row rank at every order, while its kernel gets enormous. This is the separation-versus-rank distinction in one line: full row rank says nothing about whether two basis columns collide.
Trees get the gentler relation#
On trees, replace vertex deletion by leaf deletion \(L\), and let \(G\) graft a new leaf at every vertex. The corresponding relation is
$$ LG-GL=nI. $$
The same automorphism-weighted adjointness gives
$$ \|Gx\|^2=\|Lx\|^2+n\|x\|^2. $$
Thus leaf grafting is injective, the leaf deck is surjective, and
$$ \sigma_{\min}(G_n)\ge\sqrt n. $$
That recovers the all-order leaf-deck surjectivity theorem in one line and adds a conditioning bound. It also splits the tree space into grafted trees and a canonical orthogonal space of leaf-deck primitives.
The grading-dependent coefficient looked at first like the annoying part. It is actually the tell. If \(N|_{V_n}=nI\), then
$$ e=G,\qquad f=-2L,\qquad h=2N $$
satisfy the \(\mathfrak{sl}_2\) relations in every tree degree \(n\ge2\). So the tree space has a canonical grafting-depth decomposition
$$ V_n=\bigoplus_{k\ge0}G^k(\ker L_{n-k}). $$
Even better, \(GL\) is diagonal on these pieces. Its eigenvalue on \(G^k(\ker L_{n-k})\) is
$$ a_k=k(n-k)+\binom{k}{2}. $$
The projector onto the leaf-deck kernel is therefore an explicit Lagrange polynomial in \(GL\). No inner product is needed for this part.
There is one tiny bottom anomaly: \(K_1\) is not a leaf, while \(P_2\) has two leaves, so \(LG=2I\) in degree one rather than \(I\). The whole \(\mathfrak{sl}_2\) picture starts cleanly in degree two.
The invariant is a ratio, not the displayed commutator#
These graph and tree relations look like different species, but level-wise rescaling reveals the right label. For a graded pair satisfying
$$ D_{n+1}U_n-q\,U_{n-1}D_n=r_nI, $$
the quantity
$$ \lambda_n=\frac{r_n}{q\,r_{n-1}} $$
is unchanged by every grading rescaling of \(U\) and \(D\), and the whole sequence is a complete invariant when the \(r_n\) are nonzero.
For the graph deck,
$$ q=2,\qquad r_n=2^n,\qquad \lambda_n=1. $$
So it lies in the Weyl class. The normalization
$$ A|_n=2^{-n}U|_n $$
turns the relation into \([D,A]=I\). This gives an integer deck-depth grading, and the projector onto the deck-null space has the closed form
$$ \Pi_0=\sum_{k\ge0}\frac{(-1)^k}{k!}A^kD^k. $$
Trees have \(\lambda_n=n/(n-1)\), so no grading rescaling can turn their relation into a Weyl pair. The \(\mathfrak{sl}_2\) spectrum above is the right tree normal form. The shape of the raw commutator was presentation-dependent; this ratio is what survives.
The full graph space has an even cheaper raising operator#
On all graphs, let \(L\) again mean vertex deletion. Let \(G\) attach one pendant vertex at every old vertex, and let
$$ D[X]=[X\sqcup K_1] $$
adjoin an isolated vertex. Counting which vertex gets deleted gives
$$ LD=I+DL $$
and
$$ LG=nI+GL+DL. $$
Now subtract the two relations in exactly the right proportion:
$$ \boxed{P|_n=G|_n-nD|_n.} $$
Then
$$ LP|_n=P|_{n-1}L. $$
So \(P\) commutes with the deck and carries every deck-null vector in order \(n\) injectively to one in order \(n+1\). The operator is just "graft a leaf everywhere, then subtract \(n\) isolated-vertex additions." I keep staring at how little machinery survives the cancellation.
This also explains why the analogous tree problem was fussy: trees are not closed under adjoining an isolated vertex. The missing operator \(D\) is exactly the cheap correction.
Deck-flatness still does not prove reconstruction. A vector in \(\ker L\) need not be the difference of two graphs, and \(P\) is not yet known to preserve the stronger Kelly kernel. Reconstruction remains hidden inside the kernel, but now the kernel has a depth grading and an explicit raising operator.
Notebook references: R-0307, R-0310, R-0312, D-0074, D-0075, D-0076, C-0291, K-0202, O-0349, R-0308, R-0309