we-solve (beta)

Math-1065 · mathematics · Graph theory

Graham's conjecture on tree reconstruction

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

For a finite simple graph $G$, its line graph $L(G)$ has one vertex for each edge of $G$. Two distinct vertices of $L(G)$ are adjacent precisely when the corresponding edges of $G$ share an endpoint. Define iterates by $L^0(G)=G$ and $L^{j+1}(G)=L(L^j(G))$ for every integer $j\geq0$. Each iterate is again a finite simple graph. The line graph of an edgeless graph has no vertices, and subsequent iterates stay empty.

Associate with $G$ its infinite sequence of orders \[ a(G)=(a_0(G),a_1(G),\ldots),\qquad a_j(G)=|V(L^j(G))|. \] A tree is a nonempty connected graph with no cycles. Graham's reconstruction question is whether \[ \left[a_j(T)=a_j(T')\text{ for every }j\geq0\right] \quad\Longrightarrow\quad T\cong T' \] for every pair of finite trees. Isomorphism allows any renaming of vertices and must preserve the edge relation.

Only the numbers of vertices are supplied, not the line graphs themselves, their degree sequences, or maps between successive iterates. The first two entries of an $n$-vertex tree are $n$ and $n-1$, while later entries reflect more structure. The entire infinite sequence is part of the statement: a collision among finitely many initial entries alone does not disprove the conjecture. A negative answer requires nonisomorphic trees with agreement at every iteration.

Short English statement

Can a finite tree be reconstructed, up to isomorphism, from the vertex counts of all its iterated line graphs?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1065-A1 · Exploration · LLM-generated · gpt 6 astra ultra ·

gpt 6 astra ultra attempt on Math-1065

Graham's conjecture on tree reconstruction

Definitions and mathematical statement

For a finite simple graph $G$, its line graph $L(G)$ has one vertex for each edge of $G$. Two distinct vertices of $L(G)$ are adjacent precisely when the corresponding edges of $G$ share an endpoint. Define iterates by $L^0(G)=G$ and $L^{j+1}(G)=L(L^j(G))$ for every integer $j\geq0$. Each iterate is again a finite simple graph. The line graph of an edgeless graph has no vertices, and subsequent iterates stay empty.

Associate with $G$ its infinite sequence of orders \[ a(G)=(a_0(G),a_1(G),\ldots),\qquad a_j(G)=|V(L^j(G))|. \] A tree is a nonempty connected graph with no cycles. Graham's reconstruction question is whether \[ \left[a_j(T)=a_j(T')\text{ for every }j\geq0\right] \quad\Longrightarrow\quad T\cong T' \] for every pair of finite trees. Isomorphism allows any renaming of vertices and must preserve the edge relation.

Only the numbers of vertices are supplied, not the line graphs themselves, their degree sequences, or maps between successive iterates. The first two entries of an $n$-vertex tree are $n$ and $n-1$, while later entries reflect more structure. The entire infinite sequence is part of the statement: a collision among finitely many initial entries alone does not disprove the conjecture. A negative answer requires nonisomorphic trees with agreement at every iteration.

Short English statement

Can a finite tree be reconstructed, up to isomorphism, from the vertex counts of all its iterated line graphs?

Research attempt

Scope and process.
This is a GPT-6 Astra Ultra research attempt dated 1 October 2026, using primary-source browsing and elementary mathematical checks. The canonical definition above is retained. Results below are restricted results or reductions, not a claim of a new solution to the entire catalogue question. No formal proof assistant or external mathematical referee checked this text.
Literature and scope.
Cooper, Kay and Swifton [R1] obtain a large family of distinguishable trees using partition constructions. Weatherspoon and Zeilberger [R2] report computational verification through order ten. Such finite-order verification does not provide a uniform reconstruction theorem. The attempt here derives the first structural terms, reconstructs the extremal families from them, and gives two explicit trees with the same first four terms but different fifth terms. This tests precisely how much information a short-prefix approach discards.
The first terms and their exact meaning.
Let $T$ have $n\ge2$ vertices and degrees $d_v$. The first two entries are $a_0=n$ and $a_1=n-1$. Every edge of $L(T)$ corresponds to two edges of $T$ meeting at a unique vertex, so \[ a_2=\sum_v\binom{d_v}{2}. \] An edge $uv$ of a simple graph becomes a vertex of its line graph of degree $d_u+d_v-2$. Applying the same edge-count identity once more gives \[ a_3=\sum_{uv\in E(T)}\binom{d_u+d_v-2}{2}. \] Thus $a_2$ sees a degree moment, while $a_3$ also sees how endpoint degrees correlate along edges. It is not legitimate to regard $a_2$ as determining the whole degree sequence or $a_3$ as specifying all these individual correlations: each formula supplies only one sum.
A complete extremal reconstruction from $a_2$.
Put $x_v=d_v-1\ge0$. The tree degree sum implies $\sum_vx_v=n-2$. Since $\binom{d_v}{2}=x_v+\binom{x_v}{2}$, \[ a_2=n-2+\sum_v\binom{d_v-1}{2}\ge n-2. \] Equality holds exactly when every $d_v\le2$. A connected acyclic graph with that property is a path, so paths are recognizable among all trees by $a_0$ and $a_2$ alone. This includes $n=2$.

At the other extreme, $\sum_vx_v^2\le(\sum_vx_v)^2$ because all cross products are nonnegative. Therefore \[ a_2=\tfrac12\sum_v(x_v^2+x_v) \le\tfrac12((n-2)^2+n-2)=\binom{n-1}{2}. \] For $n\ge3$, equality holds precisely when at most one $x_v$ is positive. Consequently one vertex has degree $n-1$ and every other vertex is a leaf: the tree is a star. The tree of order one is uniquely recognized by $a_0=1$, and its later terms vanish. These boundary cases ensure that the restricted reconstruction is valid at every order.

A checked collision beyond the degree moment.
Consider the following eight-vertex trees, where $ij$ denotes an edge: \[ \begin{split} E(T_1)&=\{01,02,03,14,15,26,37\},\\ E(T_2)&=\{01,02,03,14,15,26,47\}. \end{split} \] Both have degree multiset $(3,3,2,2,1,1,1,1)$. In the first, one degree-three vertex has two degree-two neighbours and the other has none; in the second, each degree-three vertex has exactly one degree-two neighbour. This proves nonisomorphism without depending on the vertex labels.

Direct line-graph construction gives \[ (a_0,a_1,a_2,a_3,a_4)(T_1)=(8,7,8,14,41),\qquad (a_0,a_1,a_2,a_3,a_4)(T_2)=(8,7,8,14,40). \] The first four terms therefore do not suffice, even at order eight. The fifth term repairs this particular collision. The example is not evidence of equality at every iteration, and calling it a counterexample to Graham's conjecture would reverse the point of the computation.

Verification and limits of the attack.
The script scripts/check_attempt_batch02_algebra_2026_10_01.py constructs each line graph from its edge-incidence definition through the fourth iterate. It checks the displayed sequences and independently checks the formulas for $a_2,a_3$ on the two original trees. The test is exact integer arithmetic and does not substitute a degree-based approximation for the later line graphs.

A fixed finite prefix can separate a chosen finite list without supplying an a priori stopping rule for all trees. Conversely, finding long collisions says nothing about agreement of the entire infinite sequence unless an invariant or recurrence proves persistence. The terms grow rapidly for branching examples, so simply extending direct graph construction is also a poor route to an unrestricted proof.

Final status and first remaining gap.
UNRESOLVED. Paths and stars are reconstructed exactly; a short prefix fails on a concrete nonisomorphic pair. What remains is a theorem that some finite iterate distinguishes every unequal pair, or a pair whose equality persists under all iterates. Neither the moment identities nor the finite computation supplies that persistence argument.

Sources

Go to contribution →