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

I extended the check of a conjecture of Alavi, Malde, Schwenk and Erdős from every tree with up to 29^▲ vertices to every tree with up to 32. The three new sizes hold about 165 billion^▲ trees, about 19^▲ times as many as all the smaller sizes together, and every one has a unimodal independence sequence (the counts rise, then fall). (A ▲ after a number links to a note about it at the bottom of the page.) The rest of this page explains the test, how the check was done, and where it stops short of a proof.

Draw a tree: a set of dots, called vertices, joined by lines, all in one piece, with no loops. A tree's size is its number of vertices. Now count the ways to pick dots so that no two picked dots are joined by a line. There is one way to pick no dots at all. 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 1, 5, 6, 1: it goes up, then down.

In 1987, Alavi, Malde, Schwenk and Erdős conjectured that this happens for every tree, and every forest (a collection of trees): once the row starts going down, it never goes back up. It may stay level for a while. A row like that is called unimodal (it has one peak). This is problem 993 on erdosproblems.com, the public list of Erdős problems, and it was open when this check finished, on August 4, 2026. (Status as of November 7, 2026: two proof claims were listed on erdosproblems.com, on September 21, 2026^▲ and September 27, 2026^▲; the first covers only forests above some size, the second every forest. In October a Lean version of the second claim's revised proof, a version that a computer checks step by step, was accepted by both proof checkers of Palomar, a public registry of such proofs. Lean confirms that the argument proves its formal statement; that statement was taken from a public library of formal problem statements, where a reviewer not involved in the proof had approved it. Neither paper has been refereed, and neither cites this check. teorth/erdosproblems, the community database of Erdős problems on GitHub that Terence Tao maintains, still records the problem as open, with the label "falsifiable" (its term for open, with a single counterexample enough to disprove it); it may not have been updated. erdosproblems.com itself stopped showing whether problems are open or solved on October 6, 2026. If the all-forests proof holds, this check is an independent computation that agrees with it on every tree up to its size. The details are under What happened next, at the end.)

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. Earlier computations had checked every tree with up to 29 vertices: the forum user JakeMallen reported it on the problem's forum on January 7, 2026, and Brett Reynolds posted code and results for the same range there on March 12, 2026 (GitHub repository BrettRey/erdos-problem-993), with a preprint on Zenodo that month. I took the check to 32 vertices. My own runs scanned the sizes 20, 22 and 24 to 32; the other sizes up to 29 rest on those earlier checks. Trees are counted by shape (unlabeled: two trees that differ only in how the dots are numbered count once). The conjecture held for every tree checked, including all 109,972,410,221 trees with 32 vertices.

Animation, no sound. An empty grid of small squares appears. First about 9 squares fill in grey: these are all the trees with 1 to 29 vertices, which earlier computations checked. Then, in the accent colour, about 15 squares fill in for the trees with 30 vertices, about 40 for 31 vertices and about 110 for 32 vertices, each size a little darker than the one before. A counter above the grid climbs to 165,134,111,053, the exact number of trees with 30, 31 or 32 vertices, and a green check mark appears with the words no counterexample. One square stands for about one billion trees.

How fast the number of trees grows#

Each extra vertex means about two and three-quarter times as many trees as the size before:

So the largest size alone had about twenty times as many trees as the old limit. All the sizes up to the old limit together hold 8,691,747,673 trees; the three new sizes hold about 165 billion^▲, about 19^▲ times as many.

How the check was done#

Who did what: when I asked for open problems that one computer could make progress on, Claude agents (Anthropic) working under my direction put this one on a shortlist, and I asked them to take the check past the old limit. The agents chose the method, wrote the program, ran it, and compared its tree counts with the OEIS list described below; they also drafted the forum comments and the pull request text. I read the results and the drafts, posted the forum comments from my own account, and had the pull request text checked again before approving it.

The program 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. The largest size was split into 16 parts, each taking a share of the trees; the parts ran side by side on one computer, and together they took about 23^▲ hours of wall-clock time. 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 rescanned every tree with 28 and with 29^▲ vertices, using code written separately from Brett Reynolds's: its tree counts matched his published counts exactly, and, as in his run, no tree broke the pattern. 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. The separate rescan covered only sizes 28 and 29. For 30, 31 and 32 vertices, the new sizes, the results rest on this one program and on its exact match with the OEIS tree counts.

There was one false alarm along the way. In July 2026, during the 30-vertex 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 vertices, so a search for one can start above that size. It does not settle forests, which the conjecture also covers: a forest's row of counts is the product of its trees' rows, multiplied as polynomials are (each entry is a sum of products; for two separate dots, 1, 1 times 1, 1 gives 1, 2, 1), and multiplying rows that each have a single peak can produce one that does not, so a forest could in principle fail even if every tree passes.

I posted the results as comments in the problem's forum on erdosproblems.com, in two steps. (On October 6, 2026, the site paused new comments and proof claims on its problems; the existing ones, these included, stay up as an archive.) The first comment, dated August 2, 2026 on the forum, covered every tree with 30 and 31 vertices; the run for 32 vertices had not started yet. That run finished on August 4, and the second comment, with the result for 32 vertices, is dated August 9, 2026 on the forum. 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).

For specialists#

Erdős Problem #993, posed by Alavi, Malde, Schwenk and Erdős (The vertex independence sequence of a graph is not constrained, Congressus Numerantium 58, 1987), 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. Products of log-concave sequences stay log-concave (Hoggar, 1974), so a forest can fail only if one of its trees is not log-concave, and such trees exist. 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 number for the star (Prodinger and Tichy, 1982, showed that the star has the most among trees of a given size), 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, this independent implementation rescanned n = 28 and n = 29: the tree counts match Reynolds's exactly, with no failures. This is an exhaustive check up to the stated order and not a proof; it says nothing about larger orders, which only a proof can cover.

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}
}