---

Claim. As the zbMATH review Zbl 0624.05028 (A. Tucker) states the paper's results: if $G$ is a nonempty graph in which every vertex set $S$ with at most $2n-2$ vertices has $|N(S)|\ge(d+1)|S|$, where $N(S)$ is the set of neighbors of $S$, then $G$ contains every tree with $n$ vertices and maximum degree at most $d$; and for fixed $d$ and any real $0<s<1$, for every $n$ there is a graph with $O(n)$ edges every subgraph of which with a fraction $s$ of its edges contains every tree with $n$ vertices and maximum degree at most $d$. Taking $s=\frac12$, one color class of any $2$-coloring of that graph's edges has at least half its edges, so $\hat r(T)=O_d(n)$ for every such tree $T$ (an elementary step of this corpus). Draganić and Petrova (2025, p. 2) quote the result in this form: "for every tree $T$ of bounded degree on $n$ vertices, $\hat r(T)=O(n)$".

Covers. The statement of Problem 559 for trees of maximum degree at most $d$, for every $d$; paths are the case $d=2$. Not covered: graphs with cycles. The statement fails in general at maximum degree three (the pages Rödl and Szemerédi 2000 and Tikhomirov 2022).

Dating. The page is dated by the issue month of the journal record (Combinatorica 7 (1987), no. 1, March 1987, per the Crossref record); the day in the page name is a placeholder.

Acceptance. Refereed: Expanding graphs contain all small trees, Combinatorica 7 (1987), no. 1, 71--76. The site's curator, T. F. Bloom, credits the tree case to this paper in the problem's commentary, but the DISPROVED label settles the problem in the negative and credits no positive sub-claim, so the credit is not reviewed evidence.

Read depth. The paper is not held here; the statement is taken from the zbMATH review and agrees with the quotation of Draganić and Petrova. No proof is covered, and nothing is independently reviewed in this corpus.

Depends on. Nothing in this wiki; the result is the paper's own theorem.