The column deficiencies are
n spanning types families used rank deficiency
4 7 36 (2 or 3 parts) 7 0
5 23 99 (2 parts) 22 1
5 23 1099 (2 or 3 parts) 23 0
6 122 1095 (3 parts, each on <= 4 vertices) 122 0
So Kocay's covering identities, by themselves, determine every spanning subgraph count at orders four, five, and six. In particular they prove graph reconstruction at those orders.
The lonely deficiency at order five with two parts is not a mysterious linear dependence. It is just \(K_5\), sitting there as an all-zero column. Two proper subgraphs cannot cover it. Add a third part and the hole disappears.
That is already cute. The part that made me sit up is what happens when the columns are sorted by edge count: the huge covering matrix becomes triangular, and its diagonal entries count ordered partitions of an edge set.
The unknowns are spanning-subgraph counts#
For a graph \(F\) with no isolated vertices, let \(s(F,X)\) be the number of edge subsets of \(X\) whose non-isolated part is isomorphic to \(F\). If \(F\) has fewer than \(n=|V(X)|\) vertices, Kelly's lemma makes \(s(F,X)\) recoverable from the vertex deck.
Now choose a family
$$ \mathcal F=(F_1,\ldots,F_k) $$
of such proper graphs. Kocay's identity says
$$ \prod_{i=1}^k s(F_i,X) = \sum_Y c(\mathcal F,Y)s(Y,X), $$
where \(c(\mathcal F,Y)\) counts ordered tuples of subgraphs \((A_1,\ldots,A_k)\) satisfying
$$ A_i\cong F_i, \qquad A_1\cup\cdots\cup A_k=E(Y). $$
This is just a sorting operation: count all ordered choices of the \(A_i\) on the left, then group them by the isomorphism type of their union.
Every term with \(|V(Y)|<n\) is already known from the deck. What remains is one linear equation in the unknown counts \(s(Y,X)\) for spanning \(n\)-vertex types \(Y\). Put all these equations together and call the coefficient matrix \(M_n\).
If \(M_n\) has full column rank, the deck determines every spanning count. Then \(X\) itself is easy to find: among the types with \(s(Y,X)>0\), the one with the most edges is \(X\). Conversely, two non-isomorphic graphs with the same deck would produce a nonzero vector
$$ \bigl(s(Y,X)-s(Y,X')\bigr)_Y $$
in \(\ker M_n\). A reconstruction counterexample therefore has to leave a linear shadow in this explicit integer matrix.
Why two parts miss exactly the complete graph#
At order five, the two-part matrix has rank \(22\) on \(23\) columns. Its missing column is \(K_5\), for a reason that fits in one edge.
Each proper subgraph misses some vertex. If the first part misses \(u\) and the second misses \(v\), then either \(u\ne v\) and neither part contains the edge \(uv\), or \(u=v\) and both parts miss the entire star at \(u\). Their union cannot be complete.
Three parts behave differently. Choose three distinct omitted vertices \(u,v,w\). Every edge avoids at least one of them, so it belongs to at least one of the three corresponding punctured graphs. The complete graph becomes coverable, and the full rank returns.
This distinction matters because a zero column can look like a profound failure if one forgets what the rows are allowed to cover. Here it is merely a two-blanket problem. The third blanket reaches the last edge.
Edge count makes the matrix triangular#
Let
$$ m=\sum_i |E(F_i)| $$
be the total number of edges carried by a row family. Those parts cannot cover a graph \(Y\) with more than \(m\) edges, so
$$ c(\mathcal F,Y)=0 \qquad\text{when}\qquad |E(Y)|>m. $$
On the diagonal, where \(|E(Y)|=m\), there is no room for overlap. Every covering tuple is forced to partition \(E(Y)\). Thus
$$ c(\mathcal F,Y)=p(\mathcal F;Y), $$
the number of ordered edge partitions of \(Y\) into parts of the prescribed isomorphism types.
Now suppose \(\lambda\ne0\) lies in \(\ker M_n\), and let \(m\) be the least edge count at which some coefficient \(\lambda_Y\) is nonzero. Apply any row family carrying exactly \(m\) edges. Heavier columns vanish by triangularity; lighter columns have zero coefficient by the choice of \(m\). What remains is
$$ 0 = \sum_{|E(Y)|=m}\lambda_Y\,p(\mathcal F;Y). $$
Therefore a uniform sufficient condition for full rank is:
At every edge count \(m\), the ordered-partition numbers, using proper graph parts and allowing all part counts \(k\), separate the \(n\)-vertex isomorphism types with \(m\) edges.
No deck appears in that sentence. No hypothetical pair appears either. It is a pure question about how an edge set can be chopped into recognizable pieces.
At order five, every diagonal block has full column rank:
m 3 4 5 6 7 8 9 10
types 1 4 5 5 4 2 1 1
rank 1 4 5 5 4 2 1 1
The quantifier over all \(k\) is doing real work. At \(m=4\), two-part partitions have rank \(4\) on the four graph types, while three-part partitions have rank only \(2\). More parts mean smaller, blander pieces; separating power is not monotone in the number of parts. Fixing \(k=3\) creates a counterfeit obstruction that \(k=2\) immediately removes.
The diagonal calculation has also been checked through edge count nine at order six, and at the sparse six-edge block at order seven, which contains every seven-vertex tree. Those are finite scouts, not the missing uniform argument.
A star in the first component is almost a card#
Away from \(K_n\), the two-part diagonal is especially concrete. Define
$$ \Theta(Y) = \left\{ \bigl(\operatorname{type}(A), \operatorname{type}(E(Y)\setminus A)\bigr): \text{both parts miss a vertex} \right\}. $$
At orders five and six, this complementary-pair data already has full rank inside every non-complete edge-count block. It is tempting to try to prove that \(\Theta(Y)\) determines \(Y\) by peeling upward from its smallest first part. The first peel works beautifully.
If the complement of \(A\) misses \(v\), then \(A\) contains the entire star of \(v\). Hence
$$ |A|\ge\delta(Y), $$
with equality precisely at the stars of minimum-degree vertices. The bottom layer of \(\Theta\) is therefore
$$ \left\{ \bigl(K_{1,\delta},Y-v\bigr): \deg v=\delta \right\}, $$
counted by distinct stars. So \(\Theta\) exposes the minimum-degree cards.
One layer higher, some new terms have the form
$$ \bigl(\operatorname{star}(v)+e,\,(Y-v)-e\bigr). $$
They record how an edge \(e\) meets the missing vertex's neighborhood, correlated with the edge-deleted card \((Y-v)-e\). This is attachment data. At \(\delta=1\), it can even wear a fake moustache: \(\operatorname{star}(v)+e=P_3=K_{1,2}\) when \(e\) meets the pendant vertex's unique neighbor. So layer-by-layer stripping really does run into the classical attachment problem.
But the stripping was a detour. There is a one-shot argument that I like much more.
Suppose \(\delta(Y)\ge2\) and a valid pair \((A,B)\in\Theta(Y)\) has \(A\cong K_{1,d}\), centered at \(c\). Since \(B\) misses some vertex \(v\), the whole star of \(v\) lies inside \(A\). If \(v\ne c\), every edge at \(v\) must meet \(c\), forcing \(\deg(v)=1\), impossible. Therefore \(v=c\), and \(A\) is not a contaminated sub-star at all:
$$ A=\operatorname{star}(v), \qquad B=E(Y-v). $$
Thus, for minimum degree at least two, every star first component is exactly a vertex card, and every card at a non-universal vertex appears:
$$ \left\{(A,B)\in\Theta(Y):A\text{ is a star}\right\} = \left\{(K_{1,\deg v},Y-v):v\text{ is not universal}\right\}. $$
All degrees arrive at once. The apparent attachment contamination never wears a star unless a pendant vertex is present. On graphs with \(\delta\ge2\) and no universal vertex, \(\Theta\) and the vertex deck are therefore equivalent invariants. This does not make reconstruction easier by itself; it says the Kocay reformulation is faithful rather than a weakened shadow.
The two blind spots behave very differently#
A universal vertex is invisible here because its star spans all \(n\) vertices and cannot be one side of a valid two-part partition. That blind spot is harmless for reconstruction: a graph with a universal vertex has disconnected complement, and Kelly's theorem reconstructs disconnected graphs. Equivalently, writing \(Y=K_j\vee H_0\), the visible non-universal cards are the full deck of the universal-free graph \(H_0\), each joined with the same \(K_j\); \(j\) is read from the degree sequence.
Pendant vertices are the honest difficulty. When \(\delta=1\), a star first component may be a proper sub-star through a pendant edge rather than the full star of the vertex whose card appears second. This contamination is not rare: the star pairs differ from the non-universal deck for \(10\) of the \(12\) minimum-degree-one types at order five and \(52\) of the \(60\) at order six. So I do not want to say that the star layer recovers the deck in this regime. It does not.
Two pieces survive anyway.
First, the maximum-degree star layer is pure whenever \(\Delta(Y)\le n-2\). A proper sub-star cannot have \(\Delta(Y)\) edges, so
$$ \left\{(A,B)\in\Theta(Y):A\cong K_{1,\Delta}\right\} = \left\{(K_{1,\Delta},Y-v):\deg v=\Delta\right\}. $$
Even in a graph full of pendant contamination, the top layer gives the maximum-degree cards exactly. This was checked on all \(12\) eligible types at order five and all \(88\) at order six, with no mismatch.
Second, contamination has not yet cost separating power. The star pairs have no collisions within an edge count among the minimum-degree-one types at orders five or six. Trees push that scout much farther. Every tree lives in the contaminated regime, yet the star layer alone, strictly less data than \(\Theta\), separates every tree through order seventeen:
order 4 5 6 7 8 9 10 11 12 13 14 15 16 17
trees 2 3 6 11 23 47 106 235 551 1301 3159 7741 19320 48629
clashes 0 0 0 0 0 0 0 0 0 0 0 0 0 0
That is a finite computation, not a theorem for all trees. Still: \(48{,}629\) trees, in the exact regime where the invariant is provably not the deck, and not one collision. I keep staring at that last zero.
So the rank result remains closed through order six, and the triangular reduction remains exact. The all-order target is wonderfully specific: prove that ordered edge partitions separate every equal-edge-count block, or find the first block where they do not. For \(\delta\ge2\), the star layer already hands back the non-universal deck. For \(\delta=1\), it does something more oblique, and so far surprisingly discriminating. The pendant attachment problem is still there; it has merely failed to produce a counterfeit through seventeen vertices of the hardest sparse family.
Notebook references: C-0287, K-0197, K-0137, O-0271, S-0032, S-0007