Checking an Erdős conjecture on every tree, three sizes further than before

Draw a tree: a set of dots joined by lines, all in one piece, with no loops. Now count the ways to pick dots so that no two picked dots are joined by a line. Count the ways to pick one dot, then two, then three, and so on, and write the counts in a row. For a straight path of five dots, there are 5 ways to pick one, 6 ways to pick two, and 1 way to pick three (both ends and the middle), so the row is 5, 6, 1: it goes up, then down.

In 1987, Alavi, Malde, Schwenk and Erdős conjectured that this happens for every tree: the row never goes down and then back up again. It may stay level in places, but there is never a second peak. Nobody has proved it. It is problem 993 on the public list of Erdős problems.

A conjecture about every tree cannot be settled by checking trees one by one, since there are infinitely many. It can be checked for every tree up to a given size, which shows where a counterexample could still be hiding. An April 2026 computation (arXiv:2604.18824, with code in the GitHub repository BrettRey/erdos-problem-993) had checked every tree with up to 29^▲ dots. I took the check to 32 dots. The conjecture held for every tree checked, including all 109,972,410,221 trees with 32 dots.

How fast the number of trees grows#

Each extra dot means a bit under three times as many trees as the size before:

So the largest size alone had about twenty times as many trees as the old limit.

How the check was done#

Claude, the AI model I work with, wrote and ran the program with me. It generated every tree of each size with nauty, a standard graph-generation package, worked out each tree's row of counts exactly, and checked that the row never rises again after falling. It handled one tree at a time on one machine. The largest size took about 23^▲ hours of wall-clock time, in 16 separately run parts. Any tree that broke the pattern would have been printed. None was.

Two checks back up the claim that every tree was covered. First, before going past the old limit, the program reproduced the earlier computation's tree counts at sizes 28 and 29^▲ exactly, using code written separately from theirs. Second, at every size, the number of trees the program produced matched the known number of trees of that size, which is recorded in the OEIS (the Online Encyclopedia of Integer Sequences) as A000055. That match would catch a generator that lost or added trees overall. It could not, on its own, catch one tree skipped and another repeated in its place; nauty's generator is built to produce each tree exactly once, and the count match confirms the totals.

There was one false alarm along the way. In July 2026, during the 30-dot run, a search of the program's output for the word VIOLATION matched the program's own all-clear line ("no VIOLATION lines above"), and it took twenty minutes to confirm there was no counterexample. Since then, searches match only lines that begin with that word.

What it shows, and where it is posted#

This does not prove the conjecture. It shows that any tree that breaks the pattern has more than 32 dots, so a search for one can start above that size. It says nothing about forests (collections of several trees), which the original conjecture also covers.

I posted the result as a comment on the problem's public page. The code, the count for each size and instructions to reproduce the run are in a public repository archived with a DOI (a permanent, citable identifier). On August 6, 2026, Terence Tao, who maintains a crowdsourced database of Erdős problems on GitHub, merged a contribution adding the OEIS cross-reference for problem 993, which cites this check. Merging it records the link; it is not an endorsement of the result.

For specialists#

Erdős Problem #993, posed by Alavi, Malde, Schwenk and Erdős, conjectures that the independence sequence of every tree (and forest) is unimodal. This check covers trees only; unimodality is not preserved under products of polynomials, so forests on the same number of vertices are not implied. Trees were generated with nauty's gentreeg and streamed as edge lists. For each tree, the independence polynomial was computed exactly with the standard in/out subtree dynamic program, using 64-bit integer coefficients; a tree on 32 vertices has at most 2^31 + 1 independent sets (the star), so no coefficient can overflow. The scanned sequence includes the constant term, and the scan flags only a strict increase after a strict decrease, so plateaus are allowed. Large orders were split into 16 parts using gentreeg's residue classes. At every order the number of trees scanned matches A000055. Before extending, the n = 28 and n = 29 tree counts of the earlier computation were reproduced exactly by this independent implementation. This is an exhaustive check up to the stated order and not a proof; the conjecture remains open for larger orders.

For readers in software:how the software was built, and which parts you could reuse

If you check every case of something and the total number of cases is already known, compare your count with that total and fail the run when they differ. Printing the count to a log is not enough. A generator that drops or duplicates cases on balance still reports zero failures, and comparing the count with the known total is the check that catches it. It will not catch a drop and a duplicate that cancel, so it works best alongside a generator designed to produce each case once.

@misc{orden2026treelevelsequenceunimodality,
  author       = {Tyler Satchel Orden},
  title        = {Checking an Erdős conjecture on every tree, three sizes further than before},
  year         = {2026},
  howpublished = {Cyborg Mathematics},
  url    = {https://cyborgmathematics.com/results/tree-level-sequence-unimodality}
}