Let T be a tree of order n≥ 3. For a graph G of order n, write delta_k(G) for the coefficients of its distance characteristic polynomial and define the normalized coefficients d_k(G)=|delta_k(G)|/2^n-k-2, for 0≤ k≤ n-2. A sequence is unimodal if it is nondecreasing up to some index and nonincreasing thereafter. Graham–Lovász's conjecture. The sequence d_0(T),…,d_n-2(T) is unimodal and its peak occurs at lfloor n/2 rfloor. The conjecture concerns the shape of the coefficients of the distance characteristic polynomial of a tree. Its prescribed peak location was disproved by Collins in 1985, although unimodality is known for stars and paths; hence the conjecture as stated is refuted.

The Graham–Lovász conjecture on unimodality of normalized tree coefficients

Let $T$ be a tree of order $n\geq 3$ . For a graph $G$ of order $n$ , write $\delta_k(G)$ for the coefficients of its distance characteristic polynomial and define the normalized coefficients

d_k(G)=|\delta_k(G)|/2^{n-k-2},

for $0\leq k\leq n-2$ . A sequence is unimodal if it is nondecreasing up to some index and nonincreasing thereafter. Graham–Lovász's conjecture. The sequence $d_0(T),\dots,d_{n-2}(T)$ is unimodal and its peak occurs at $\left\lfloor n/2\right\rfloor$ .

The conjecture concerns the shape of the coefficients of the distance characteristic polynomial of a tree. Its prescribed peak location was disproved by Collins in 1985, although unimodality is known for stars and paths; hence the conjecture as stated is refuted.

The conjecture combines unimodality of the normalized coefficients with a prescribed peak at $\lfloor n/2\rfloor$ . Collins disproved that peak location in 1985; the surviving question is the unimodality itself and the sharper Collins–Shor bounds on the peak.

Known results

Collins, 1985: the prescribed peak at $\lfloor n/2\rfloor$ is false; for paths it is asymptotically near $\left(1-1/\sqrt{5}\right)n$ .
Collins: normalized coefficients are unimodal for paths and stars.
The 2015 result proves log-concavity, hence unimodality, for every tree.
The same work gives a universal peak upper bound near $2n/3$ , a diameter-dependent lower bound, and computational confirmation through order $20$ .

2015 proof of unimodality

A 2015 paper titled Proof of a Conjecture of Graham and Lovász concerning Unimodality of Coefficients of the Distance Characteristic Polynomial of a Tree claims log-concavity and therefore unimodality of both the absolute and normalized coefficient sequences for every tree. It leaves the corrected peak-location question open; the claim is reported here as unverified.

Current status (as of September 2026): The original peak-location assertion is refuted, while unimodality is claimed proved for all trees; the corrected Collins–Shor peak-location conjecture remains open.

The Graham–Lovász conjecture on unimodality of normalized tree coefficients

Primary source

Progress summary

Solutions 0