---

Claim. Yi Zhao, Proof of the $(n/2-n/2-n/2)$ Conjecture for large $n$, Electron. J. Combin. 18 (2011), no. 1, Paper 27, 61 pp., doi:10.37236/514 (submitted 6 June 2008, accepted 22 January 2011, published 4 February 2011, this page's date). Theorem 1.6, the paper's main theorem (p. 2; result page): there is a threshold $n_0$ such that for every $n\ge n_0$, a graph of order $n$ in which at least $\lceil n/2\rceil$ vertices have degree at least $\lceil n/2\rceil$ contains every tree with at most $\lfloor n/2\rfloor$ edges. The site asks about trees on at most $n/2$ vertices under the hypothesis that at least $n/2$ vertices have degree at least $n/2$; such a tree has at most $\lfloor n/2\rfloor$ edges, and the site's hypothesis implies the rounded one because degrees and counts are integers, so the theorem answers the site's question affirmatively for every $n\ge n_0$. The threshold is existential: neither the statement nor the introduction gives a value, and the proof goes through the Regularity Lemma, so none is to be expected from it. The theorem therefore reduces the problem to a finite check, which is what the site's label DECIDABLE records; the check's extent is unknown. Construction 1.7 (p. 3; result page) shows that in Zhao's edge form the count $n/2$ of large-degree vertices cannot be lowered to $n/2-\sqrt n-2$; its tree has $n/2+1$ vertices, so it does not bear on the site's vertex form directly.

Covers. Every order $n\ge n_0$, for a threshold $n_0$ the paper does not state. What remains is the finite check of every $n<n_0$: once those orders are verified, the problem of Problem 580 is settled in the affirmative. No source on record closes any part of that remainder, and its extent is unknown because $n_0$ is not explicit. A computer-assisted verification for $n\le19$, submitted to the site's proof-claim tab in July 2026 and unreviewed, has its own claim page. The approximate theorem of Ajtai, Komlós and Szemerédi (1995), with $(1+\rho)n/2$ in both places for large $n$, is the earlier result the paper supersedes and is known here only through Zhao's Theorem 1.5.

Depends on. Nothing in this wiki: the proof is the paper's. The statements of Conjecture 1.3, Theorems 1.5 and 1.6 and Construction 1.7 (pp. 2--3) are this page's basis; the proof (Sections 3--7 and the appendix, pp. 5--61) was not read.

Acceptance. Refereed: the Electronic Journal of Combinatorics is a refereed journal (submitted 6 June 2008, accepted 22 January 2011, by its Crossref record). As context, not evidence: after a comment of 23 October 2025 on the site's discussion thread pointed to the paper, the site's curator, Thomas Bloom, relabeled the problem DECIDABLE and credits Zhao in the problem's commentary with the proof for all sufficiently large $n$ (page last edited 24 October 2025); the community database lists the problem as decidable, its record last updated 23 October 2025. The label records the reduction to a finite check without settling the problem, so the credit is not reviewed evidence. The acceptance rests on the refereed venue alone; this repository's own review is not claimed as evidence.