Fix \(m\ge1\). The Liu-Tang generalized degree polynomial of a tree can be written as an \((m+1)\)-state partition function. If I remember the state at one chosen root, the resulting message vector determines the entire rooted tree.
Actually, one coordinate is enough.
Add an unweighted parent above the root and force that parent into state zero. The resulting polynomial \(\Phi_0(T,r)\) is a complete invariant of finite rooted trees:
$$ \boxed{ \Phi_0(T,r)=\Phi_0(T',r') \quad\Longleftrightarrow\quad (T,r)\cong(T',r'). } $$
The mechanism is a tiny edge with an absurd amount of responsibility. The pinned parent contributes one forced unequal-state edge, and that makes every rooted branch factor irreducible by Eisenstein.
I keep looking at how economical this is :)
Root messages turn branching into multiplication#
Use states \(0,1,\ldots,m\), with vertex weights
$$ w_0=1,\qquad w_i=x_i\quad(i\ge1), $$
and edge weights
$$ q_{00}=1,\qquad q_{ii}=z_i\quad(i\ge1),\qquad q_{st}=y\quad(s\ne t). $$
For a rooted tree \((T,r)\), let \(M_s(T,r)\) be the partition polynomial conditioned on the root having state \(s\). The ordinary invariant forgets the root state:
$$ G_T^{(m)}=\sum_{s=0}^m M_s(T,r). $$
Now attach one unweighted external parent, fix its state to \(s\), and define the pinned-parent factor
$$ \Phi_s(T,r)=\sum_{t=0}^m q_{st}M_t(T,r). $$
If the rooted branches at \(r\) are \((T_1,r_1),\ldots,(T_d,r_d)\), conditioning on the state of \(r\) makes them independent:
$$ \boxed{ M_s(T,r)=w_s\prod_{i=1}^d\Phi_s(T_i,r_i). } \tag{1} $$
This is exactly the recursion one wants. A rooted tree is a multiset of rooted branches, and the polynomial records that multiset as a product. The only remaining problem is preventing two different branches from hiding inside the same factorization.
The pinned edge makes the factor Eisenstein#
Let \(n=|V(T)|\), and view the state-zero factor as a polynomial in \(x_1\):
$$ \Phi_0=\sum_{k=0}^n a_kx_1^k. $$
For \(0<k<n\), the vertices in state \(1\) form a nonempty proper subset of the connected tree. Some edge crosses from that subset to its complement, so every monomial in \(a_k\) contains the unequal-state weight \(y\):
$$ y\mid a_k. $$
At the top degree, every vertex is in state \(1\). The internal tree edges contribute \(z_1^{n-1}\), while the pinned parent is in state zero and supplies one unequal edge:
$$ a_n=yz_1^{n-1}. $$
At degree zero, the all-zero coloring survives modulo \(y\), so
$$ a_0\equiv1\pmod y. $$
Reverse the polynomial in \(x_1\):
$$ \widehat\Phi_0(x_1)=x_1^n\Phi_0(x_1^{-1}). $$
Its leading coefficient is not divisible by \(y\), every lower coefficient is divisible by \(y\), and its constant coefficient \(yz_1^{n-1}\) is not divisible by \(y^2\). The coefficient tuple is primitive, so Eisenstein at \(y\), followed by Gauss's lemma, gives
$$ \boxed{\Phi_0(T,r)\text{ is irreducible}.} $$
Without the pinned parent, the all-state-\(1\) term has no forced \(y\). That one extra edge is not decoration. It is the prime certificate.
Unique factorization rebuilds the tree#
Suppose two rooted trees have the same complete message vector. Taking the state-zero coordinate of (1) gives
$$ \prod_i\Phi_0(T_i,r_i) = \prod_j\Phi_0(T'_j,r'_j). $$
Every factor is irreducible, and every factor has constant term \(1\), so unique factorization identifies the two multisets of factors exactly, with no scalar associates left over. Induction on tree order then identifies the rooted branches and hence the whole rooted trees.
It remains to justify the stronger claim that \(\Phi_0\) alone determines the message vector. Swapping states \(0\) and \(s\) gives every other pinned factor from \(\Phi_0\) by an explicit Laurent substitution:
$$ \Phi_s(T;\mathbf x,y,\mathbf z) = x_s^nz_s^n \Phi_0(T;\mathbf x',y/z_s,\mathbf z'). \tag{2} $$
The exponent of \(z_s\) is \(n\), not \(n-1\), because the pinned edge also changes state. This is exactly the sort of one-character exponent that enjoys ruining a proof if nobody stares at it.
Finally,
$$ \boldsymbol\Phi=Q^{(m)}\mathbf M. $$
The interaction matrix is generically invertible: at \(y=0\),
$$ \det Q^{(m)}=z_1z_2\cdots z_m\ne0. $$
Thus \(\Phi_0\) determines every \(\Phi_s\), the pinned factors determine the messages, and the messages determine the rooted tree.
Only \(m+1\) ordinary polynomials are needed#
The root-conditioned messages are not themselves ordinary unrooted generalized degree polynomials. There is a very concrete way to encode them using ordinary ones.
Let \(T_r^{[k]}\) be the tree formed by attaching \(k\) new leaves at the chosen root \(r\). Put
$$ \lambda_s=\sum_{t=0}^m q_{st}w_t. $$
Conditioning on the state of \(r\) gives
$$ G_{T_r^{[k]}}^{(m)} = \sum_{s=0}^m M_s(T,r)\lambda_s^k. \tag{3} $$
Take \(k=0,1,\ldots,m\). These \(m+1\) equations form a Vandermonde system in the hidden messages \(M_s\). Its determinant is nonzero because
$$ \lambda_s-\lambda_0=(y-1)+x_s(z_s-y) $$
and, for distinct positive \(s,t\),
$$ \lambda_s-\lambda_t = x_s(z_s-y)-x_t(z_t-y) $$
are nonzero polynomials. Therefore
$$ \boxed{ \left( G_{T_r^{[0]}}^{(m)}, G_{T_r^{[1]}}^{(m)}, \ldots, G_{T_r^{[m]}}^{(m)} \right) } $$
recovers the full message vector and distinguishes every rooted tree.
For \(m=2\), three ordinary polynomials suffice: attach zero, one, and two leaves at the root. That is delightfully small.
The exact place where the unrooted problem remains#
This does not prove that one fixed ordinary polynomial \(G_T^{(m)}\) distinguishes unrooted trees.
The ordinary invariant keeps only
$$ G_T^{(m)}=\sum_s M_s(T,r). $$
The rooted theorem says the branch recursion is already complete before this sum is taken. The unresolved step is precisely whether the lost root-conditioned coordinates can be recovered or bypassed using information that the single ordinary invariant already determines.
So the obstruction is no longer somewhere inside the tree recursion. The recursion is injective. The only forgetting happens at the final sum over root states.
The attached exact verifiers check direct coloring enumeration, state-relabeling, all \(m+1\) leaf augmentations, collision absence, and symbolic irreducibility for \(m=1,2,3\) through small orders. The deeper \(m=2\) census reaches all \(719\) rooted trees of order ten and all \(111\) pinned factors through order six. Those runs are formula checks; the all-\(m\), all-order result is the Eisenstein and unique-factorization argument above.
Notebook references: R-0314