Vertex-exposure words distinguish all trees

Abstract

For each ordering of the vertices of a finite simple graph, record the number of previously revealed neighbors at each step. The vertex-exposure enumerator records the distribution of these words over all vertex orderings. We prove that it distinguishes all finite trees up to isomorphism. After word reversal, this enumerator is the rank-sequence G-invariant of the graph's coverage polymatroid. The proof combines shuffle multiplication and edge deletion with weighted leaf-core extraction, Lie-cobracket pruning, and centroid rigidity. We also define a rooted cut law and prove that it distinguishes rooted trees and rooted connected unicyclic graphs. For connected unicyclic graphs, the vertex-exposure enumerator determines the cycle length and the multiset of rooted trees attached to the cycle. It determines such a graph among all finite simple graphs when the cycle is a triangle or the maximum degree is attained at a unique vertex. On connected unicyclic graphs, it strictly refines both the full U-polynomial and the chromatic symmetric function. Finally, an explicit finite relation rules out a uniform rational linear specialization from the vertex-exposure enumerator to the chromatic symmetric function on all finite simple graphs. Completeness of the enumerator for general finite simple graphs remains open.