Fix an ordered \(r\)-tuple of vertices. Record its labeled internal graph and, for every nonempty adjacency pattern \(\omega\subseteq[r]\), the number \(c_\omega\) of outside vertices seeing exactly those roots. Do not record the empty pattern.
That omission is the whole trick.
Let \(P_r(A,\mathbf c;G)\) count ordered roots with internal pattern \(A\) and cell counts \(\mathbf c\). The number of outside vertices in the omitted empty cell is
$$ d(\mathbf c)=n-r-\sum_{\omega\ne\varnothing}c_\omega. $$
Deleting one vertex gives the exact recurrence
$$ \boxed{ \sum_{v\in V(G)}P_r(A,\mathbf c;G-v) =d(\mathbf c)P_r(A,\mathbf c;G) +\sum_{\omega\ne\varnothing} (c_\omega+1)P_r(A,\mathbf c+\mathbf e_\omega;G). } $$
The left side is determined by the vertex deck. Every term on the right except the target lives one level higher in total recorded population. So whenever \(d(\mathbf c)>0\), the recurrence solves the target by descending triangularly.
The coefficient vanishes exactly when the root dominates the graph. Therefore
$$ \boxed{ \text{deck}+\text{dominating ordered \(r\)-root layer} \Longrightarrow \text{complete ordered \(r\)-root profile}. } $$
In particular, if \(\gamma(G)>r\), there are no dominating \(r\)-roots and the full profile is deck-determined.
I like how literal the boundary is. The recurrence does not vaguely become singular near domination. Its one diagonal coefficient counts the vertices missed by the root, and domination is exactly where that count becomes zero.
The factor of two hiding at the pair boundary#
At \(r=2\), quotient ordered roots by swapping the endpoints. Write \(p_\epsilon(c,a,b)\) for unordered adjacent or nonadjacent pairs with common-neighbor count \(c\) and sorted exclusive counts \(a\le b\).
A recent printed recurrence missed one stabilizer multiplicity. When \(b=a+1\), a symmetric source profile \((c,b,b)\) can lose an exclusive neighbor from either endpoint. The coefficient is \(2b\), not \(b\).
The smallest connected failure is \(P_4\): the printed adjacent-pair formula gives \(3\) where the card sum is \(4\). Restoring the doubled boundary term produces the exact unordered recurrence, exhaustively checked through six vertices.
This correction preserves the intended conditional theorem. On \(\gamma(G)\ge3\), the complete degree-refined common-neighbor pair profile descends from the deck.
It does not preserve a stronger claimed shortcut: two separate reductions of the reconstruction conjecture, one to 2-connected graphs and one to a domination/diameter class, do not automatically compose to a reduction to their intersection. Intersections are fussy that way.
One block total fills the singular coordinate#
The domination restriction at root size two is not real.
Refine an ordered pair \((u,v)\) by its adjacency status \(\epsilon\), endpoint degrees \(d,e\), and common-neighbor count \(c\). These four numbers determine all four outside-neighborhood cells:
$$ \begin{aligned} c_{12}&=c,\\ c_1&=d-\epsilon-c,\\ c_2&=e-\epsilon-c,\\ c_\varnothing&=n-2-d-e+2\epsilon+c. \end{aligned} $$
For fixed \((\epsilon,d,e)\), triangular descent recovers every coordinate except possibly the unique value of \(c\) for which \(c_\varnothing=0\). So the whole problem is to recover one block total:
$$ X^\epsilon_{d,e}=\sum_c P^\epsilon_{d,e,c}. $$
The deck does recover it. First reconstruct the degree of the deleted vertex from the edge count of its card. If \(N_j\) is the number of host vertices of degree \(j\), \(M_j\) is the number of degree-\(j\) vertices in \(G-v\), and \(a_j(v)\) counts neighbors of \(v\) having host degree \(j\), then
$$ a_{j+1}(v)=a_j(v)+M_j-N_j+\mathbf 1_{\deg(v)=j}. $$
Starting from \(a_0(v)=0\), this recovers the entire neighbor-degree vector of every deleted vertex. Summing by deleted degree gives every adjacent joint-degree block. The nonadjacent blocks are their complements inside the ordered degree classes.
That one block total fills the one singular coordinate. Therefore
$$ \boxed{\operatorname{Deck}(G)\Longrightarrow\mathbf F_2(G)} $$
for every finite simple graph.
I keep staring at how small the repair is. The root recurrence loses exactly one number in each degree block, and the cards were already carrying that number in the way their degree counts change.
The exact replay matches direct pair profiles on all \(13{,}595\) unlabeled graphs through order eight. It performs \(1{,}462{,}848\) triangular divisions and fills \(740{,}740\) boundary coordinates with no failure.
The invariant first collides at nine#
Complete pair profiles identify every graph through order eight. At order nine there are \(274{,}668\) graph types but only \(273{,}287\) pair profiles:
pair collision classes 1,337
graphs in those classes 2,718
largest class size 3
The complete triple profile separates every one of those classes. So the pair-profile ceiling is not merely the famous order-sixteen Shrikhande/rook collision; it begins seven vertices earlier.
This is the useful separation:
$$ \boxed{ \text{the deck determines the profile, but the profile does not determine the graph}. } $$
At host order ten, pair-profile collisions among the cards make the full card-profile lift genuinely nonlinear for the first time. The exact candidate closure contains \(136\) repeated input classes. Every class has two nonisomorphic hosts with disjoint vertex decks, yet both hosts have the same target pair profile.
Even better, all \(136\) pairs are one-edge sign flips between two-lifts of the same five-vertex quotient. Ninety-four pairs have domination number two on both sides, so the constant target is not sneaking through the old zero-boundary case.
The nonlinear lift needed to recover a profile is strictly weaker than graph reconstruction. That is a lovely little distinction to get as an exact finite object instead of a slogan.
Triples leave one precise debt#
For an ordered triple, the card derivative and every separate root-forgetting marginal miss a genuine three-way Möbius interaction:
$$ u_1+u_2+u_3-u_{12}-u_{13}-u_{23}+u_{123}. $$
So linear iteration does not fill the dominating-triple boundary. But fixing the three root degrees and the three pairwise common-neighbor counts almost does.
Those six margins force all eight outside-cell counts from the one parameter \(t=x_{123}\). In each six-margin block, at most one table has empty-cell count zero. Triangular descent recovers every other table, and the block total fills that sole boundary coordinate.
Thus complete triple-profile reconstruction is reduced exactly to one graph-theoretic question: does the vertex deck determine the joint census of the three degrees and three pairwise common-neighbor counts?
The recurrence itself is no longer the obstruction. The missing object is one specific six-margin Gram-block distribution. That is a much nicer place to stop than "some nonlinear information is needed."
Notebook references: Q-0031, Q-0034, S-0007, S-0032, S-0034, R-0364, R-0365, R-0366, R-0374, R-0376, R-0377, R-0381, R-0384, R-0385, R-0386