Status
On this page
Status
Topics
Status
On this page
Status
Topics
If is a tree on vertices then
If is a tree on vertices then
Source: erdosproblems.com/547
An accepted solution exists. The statement is true.
DECIDABLE, the site's label (page last edited 18 January 2026), which describes the large- bound: for every tree on vertices once is large, with the threshold not explicit. The site attributes that bound both to the implication from the Erdős--Sós conjecture under the announced, unpublished Ajtai--Komlós--Simonovits--Szemerédi proof of #548 and to Zhao's alternative proof; Zhao's is the refereed one, recorded on the accepted partial claim page Zhao 2011. The label and the commentary predate the proof of #548, which the site itself marks PROVED (FORMALIZED) on 3 September 2026, and two comments in the problem's discussion, of 6 and 17 September 2026, asked for the label PROVED; no curator reply follows them. The corrected Statement, the bound for every , follows from the new proof of #548 through the Ramsey corollary; that consequence is an accepted full claim, recorded on the claim page from the 2026 proof of #548 on a third party's Lean derivation of it, announced in the problem's discussion on 17 September 2026, which this corpus built and audited (Formalization, below); the frontmatter standing, solved and proved, derives from it. The corrected Statement's exclusion of is the corpus's own correction; the site has not addressed (Notes, above). The site states the implication on its pages for #548 and #547 but has not relabeled #547; the curator posted the #548 proof claim, so the site's statement of the implication is not an independent review; the corollary has no refereed writeup; and this corpus's own review of the corollary awards no acceptance. Four more partial claims are paged: the path case of Gerencsér and Gyárfás 1967 and the double-star bound of Grossman, Harary and Klawe 1979 (both accepted, refereed), Burr's formula for trees of small maximum degree by Montgomery, Pavez-Signé and Yan 2025 (claimed, a preprint), and the independent Lean proof for large in Alexeev's repository (claimed). The same repository's two refutations at are recorded on a rejected claim page (Alexeev Literal, 2026). The star formula the site credits to Harary [Ha72] has no page: it appears in a proceedings volume the corpus has not examined, and every star on vertices is the double star , an instance the Grossman--Harary--Klawe page already covers.
Burr and Erdős ([BuEr76], p. 257) print the conjecture with no range
on , and the site's wording keeps free. Read as the site words it, it
includes the one-vertex tree , where it is false: the host is
, which has no vertex and so contains no copy of , and
. Hua Xu noted this in the site's discussion on 1 May 2026, and
two Lean developments in Boris Alexeev's repository, both of 26 August 2026,
prove the same failure (Erdos547.not_erdos_547 in
Erdos547.lean
and Erdos547b.not_literalErdos547 in
Erdos547b.lean).
It is the only failing instance: every tree on two, three or four vertices is a
path or a star, Theorem 1 of [GeGy67] gives ,
that is , and , and
the two-color star value
completes , each at most . The site reads the question
as the bound for every : its label DECIDABLE ("Resolved up to a finite
check") records that the large- bound is proved and a finite range of small
remains, the reading its editor gave in the discussion on 11 September 2025
when changing the label from solved to decidable because "the question was for
all "; the commentary credits the large- bound to the Erdős--Sós
implication and to Zhao [Zh11]. The site has not addressed , and its label
and commentary (last edited 18 January 2026) predate the proof of
#548 (3 September 2026) and the
two requests in the discussion (6 and 17 September 2026) to relabel the problem
proved. The corrected Statement excludes exactly , the one value at which,
because of its size, no host can meet the conclusion; it is the corpus's
correction, not the site's, and the formal-conjectures statement file, which
counts with the site, states the bound for as well (Formalization,
below). Under the site's wording the answer is: false at and true for
every . Under the corrected Statement the answer is yes, proved for
every by the Ramsey corollary of the #548 theorem, with
for odd (Progress, below). The problem's standing judges the corrected
Statement. The refutations answer the site's wording (every , the
one-vertex tree included), not the corrected Statement (trees on
vertices), so they do not count toward the problem's standing; they are credited
here and on
Alexeev's rejected claim page (2026).