Erdős Problem #548

Erdős problem 548. If $n\geq k+1$, must a graph with more than $(k-1)n/2$ edges contain every tree with $k+1$ vertices?

Status and source. The answer is yes. The following reconstructs the marked-permutation proof in the current exposition attributed to GPT-6 Astra, using the corrected, explicit counting maps in the illustrated exposition by Ben Golub. This is a reconstruction of that existing proof, not a claim of a new discovery or of formal verification of this file. Sources: https://www.erdosproblems.com/548 and https://www.erdosproblems.com/static/548-exp.pdf, checked 24 September 2026.

A counting theorem for rooted trees. Fix a graph $G$ on $n$ vertices. For a permutation $\pi=(v_0,\ldots,v_{n-1})$ and $1\leq j<n$, call $(\pi,j)$ marked when $v_0v_j$ is an edge. Let $B$ count all marked pairs. For a rooted tree $T$, let $C(T)$ count marked pairs whose prefix $\{v_0,\ldots,v_j\}$ contains a copy of $T$ rooted at $v_0$. Each pair is counted once, regardless of the number of copies. Then \[ B=2e(G)(n-1)!. \] We prove, by induction on $t=|T|\geq2$, that \[ B-C(T)\leq(t-2)n!. \tag{1} \] For $t=2$ the marking edge itself gives the rooted copy, so $C(T)=B$.

Removing a leaf root. Suppose the root is a leaf; let $T'$ be the tree after deleting it, rooted at its former neighbour. For each permutation discard its first marked cut counted by $C(T')$, if any. At each remaining such cut $j$, an earlier qualifying prefix contains $T'$ and does not contain $v_j$. Attach $v_j$ to its root $v_0$. This gives $T$ rooted at $v_j$. Reverse the prefix through $j$: \[ (v_0,v_1,\ldots,v_j\mid v_{j+1},\ldots) \longmapsto(v_j,v_{j-1},\ldots,v_0\mid v_{j+1},\ldots). \] The image has the same prefix vertex set, is marked, and contains $T$ at its new root. Reversing the same prefix recovers the input, so the map is injective. At most $n!$ inputs were discarded. Consequently \[ C(T')\leq C(T)+n!, \] and induction proves $1$ in this case. The reversal is performed at the retained cut, not at the earlier discarded cut.

Splitting a root with several branches. If the root has degree at least two, split its branches into two nonempty groups, producing rooted proper subtrees $T_1,T_2$ meeting only at their root. Put $t_i=|T_i|$, so $t_1+t_2=t+1$. We claim \[ C(T_1)+C(T_2)\leq B+C(T)+n!. \tag{2} \] Consider a marked pair that contains $T_1$ but does not contain $T$. Write its permutation, with its cut, as $xRX\mid Y$, where $x$ is the root and $R$ is the shortest initial block for which $xR$ contains $T_1$ rooted at $x$. If $X$ is empty discard this input. There is at most one such input per permutation.

For every other input use the map \[ xRX\mid Y\longmapsto xX\mid RY. \] It preserves the marked edge, whose endpoint is the last vertex of the nonempty block $X$. The new prefix $xX$ cannot contain $T_2$: such a copy would be disjoint, except at $x$, from a copy of $T_1$ inside $xR$, and their union would give the forbidden $T$ in the original prefix.

The map is injective. The output cut specifies $X$; in the remaining suffix read vertices after $x$, ignoring $X$, until a rooted $T_1$ first appears. This uniquely recovers $R$, by its original minimality, and the remaining vertices give $Y$. Thus \[ C(T_1)-C(T)-n!\leq B-C(T_2), \] which proves $2$. The discarded empty block is essential to this inequality.

Adding the two induction inequalities and using $2$ now gives \[ 2B\leq C(T_1)+C(T_2)+(t_1+t_2-4)n! \leq B+C(T)+(t-2)n!, \] as required.

Conclusion. If $G$ contains no copy of a particular $t$-vertex tree, then $C(T)=0$ for any rooting of that tree. Formula $1$ yields $2e(G)\leq(t-2)n$. Therefore $e(G)>(t-2)n/2$ forces every such tree. Setting $t=k+1$ proves the stated problem, including its slightly stronger integral-edge formulation. No claim about arbitrary forests is needed.

Completion estimate. The rooted counting inequality and both injective maps are proved above; the displayed problem is fully resolved. COMPLETION: 100%

The Erdős-Sós conjecture: Let $n\ge k+1$. Every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains every tree on $k+1$ vertices.

We can prove that this is true if we instead assume the graph has at least $n(k-1)+1$ edges. This result is easily proved by induction. The conjecture is that the true threshold is $\frac{k-1}{2}n+1$.

Erdős and Gallai $1959$ made the following conjecture, which if true would imply the Erdős-Sós conjecture. Let $F$ be a forest with $k$ edges and no isolated vertices. Then every graph on $n$ vertices with at least $\frac{k-1}{2}n+1$ edges contains $F$. Erdős and Gallai $1959$ proved that this is true if $F$ is a forest of $k$ independent edges.

1) “FORMAL RESTATEMENT”

Fix integers $n\ge k+1\ge 2$. The Erdős--Sós conjecture asserts:

(ES) Every graph $G$ on $n$ vertices with \[ e(G)\ \ge\ \frac{k-1}{2}n + 1 \] contains every tree $T$ on $k+1$ vertices as a (not necessarily induced) subgraph.

The problem statement also records a provable weaker sufficient condition:

(Weak) If $e(G)\ge n(k-1)+1$, then $G$ contains every tree on $k+1$ vertices.

I will give a complete proof of (Weak), and a few additional easy special cases/checks toward (ES).

2) “QUICK LITERATURE/CONTEXT CHECK”

The statement above is the classical Erdős--Sós conjecture. The file notes: - The weaker bound $e(G)\ge n(k-1)+1$ implies the conclusion and is “easily proved by induction”. - Erdős and Gallai also conjectured an analogous statement for forests; and they proved it when the forest consists of $k$ independent edges.

In what follows I will only use what is stated in the problem file, and prove the weaker bound from scratch.

3) “ATTACK PLAN”

To prove (Weak), it is enough to show that a graph with $e(G)\ge n(k-1)+1$ contains a subgraph of minimum degree at least $k$ on at least $k+1$ vertices, and then show that minimum degree $\ge k$ forces a copy of any tree on $k+1$ vertices by a greedy/inductive embedding.

For sanity, I will also brute-force check the conjectured (ES) condition for a few small $(n,k)$ where exhaustive enumeration is feasible.

4) “WORK”

Lemma 1 (Pruning to minimum degree $\ge k$). Let $G$ be a graph on $n$ vertices with $e(G)\ge n(k-1)+1$. Then $G$ has a subgraph $H$ with \[ |V(H)|\ge k+1 \quad\text{and}\quad \delta(H)\ge k. \]

Proof. Starting from $G_0:=G$, iteratively delete a vertex of degree at most $k-1$ (if one exists), together with all incident edges. This produces a sequence of graphs \[ G=G_0 \supseteq G_1 \supseteq \cdots \supseteq G_r \] where $G_r$ has minimum degree at least $k$ (or is empty).

Each deletion removes at most $k-1$ edges. If $G_r$ has $N$ vertices, then we deleted $n-N$ vertices, so \[ e(G_r)\ \ge\ e(G) - (n-N)(k-1)\ \ge\ n(k-1)+1 - (n-N)(k-1)\ =\ N(k-1)+1. \] If $N\le k$, then the maximum possible number of edges on $N$ vertices is $\binom{N}{2}$, but for $N\le k$ we have \[ \binom{N}{2} \le \binom{k}{2} = \frac{k(k-1)}{2} < k(k-1)+1 \le N(k-1)+1, \] which contradicts $e(G_r)\le \binom{N}{2}$. Therefore $N\ge k+1$. Since the procedure stops only when no vertex of degree $\le k-1$ remains, we have $\delta(G_r)\ge k$. Taking $H:=G_r$ completes the proof. $\square$

Lemma 2 (Minimum degree $\ge k$ contains every $(k+1)$-vertex tree). Let $H$ be a graph with $\delta(H)\ge k$ and $|V(H)|\ge k+1$. Then $H$ contains every tree $T$ on $k+1$ vertices as a subgraph.

Proof. We prove by induction on $k\ge 1$.

Base case $k=1$: a tree on $2$ vertices is a single edge. Since $\delta(H)\ge 1$, $H$ contains an edge.

Induction step: assume the statement holds for $k-1$, and let $T$ be a tree on $k+1$ vertices. Choose a leaf $\ell$ of $T$, and let $u$ be its unique neighbour. Let $T':=T-\ell$ be the tree obtained by deleting $\ell$; then $T'$ is a tree on $k$ vertices.

Let $H$ be as in the lemma. Since $\delta(H)\ge k$, in particular $\delta(H)\ge k-1$, and $|V(H)|\ge k+1\ge k$. By the induction hypothesis applied to $k-1$ and the tree $T'$ (which has $k$ vertices), there is an embedding $\varphi:V(T')\hookrightarrow V(H)$ such that every edge of $T'$ maps to an edge of $H$.

Let $x:=\varphi(u)$. The vertex $x$ has degree at least $k$ in $H$. In the embedding of $T'$, at most $k-1$ vertices of $H$ are already used (since $|V(T')|=k$). Among the neighbours of $x$, at most $k-1$ can lie in the used vertex set (indeed there are only $k-1$ other used vertices besides $x$ itself). Therefore $x$ has at least one neighbour $y\in V(H)$ not in $\varphi(V(T'))$.

Extend $\varphi$ to $V(T)$ by mapping the deleted leaf $\ell$ to $y$. Then the only new edge of $T$ to check is $u\ell$, which maps to $xy$, an edge of $H$ by construction. Hence $T$ embeds into $H$.

This completes the induction. $\square$

Proposition 3 (Proof of the weaker bound). If $G$ is a graph on $n$ vertices with $e(G)\ge n(k-1)+1$, then $G$ contains every tree on $k+1$ vertices.

Proof. By Lemma 1, $G$ contains a subgraph $H$ with $|V(H)|\ge k+1$ and $\delta(H)\ge k$. By Lemma 2, $H$ contains every tree on $k+1$ vertices, hence so does $G$. $\square$

Lemma 4 (The Erdős--Sós bound holds for stars). Let $k\ge 1$. If $G$ is a graph on $n$ vertices with $e(G)\ge \frac{k-1}{2}n+1$, then $G$ contains the star $K_{1,k}$.

Proof. The average degree of $G$ is $\bar d = 2e(G)/n > k-1$. Hence there exists a vertex of degree at least $\lceil\bar d\rceil\ge k$, which is the centre of a copy of $K_{1,k}$. $\square$

5) “VERIFICATION”

Fast reality check by exhaustive enumeration of graphs for a few small parameters (checking the Erdős--Sós threshold $e(G)\ge \frac{k-1}{2}n+1$): - For $(n,k)=(5,3)$ (trees on $4$ vertices; threshold $e\ge 6$) all $386$ graphs with $\ge 6$ edges contain both $P_4$ and $K_{1,3}$. - For $(n,k)=(6,3)$ (threshold $e\ge 7$) all $22{,}819$ graphs with $\ge 7$ edges contain both $P_4$ and $K_{1,3}$. - For $(n,k)=(6,4)$ (trees on $5$ vertices; threshold $e\ge 10$) all $4{,}944$ graphs with $\ge 10$ edges contain all three trees on $5$ vertices.

These computations do not prove the conjecture but are consistent with it in small cases.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Proposition 3 proves the statement with the stronger hypothesis $e(G)\ge n(k-1)+1$. Lemma 4 proves the conjectured threshold for the special case when the tree is the star $K_{1,k}$. Exhaustive checks for small $(n,k)$ (listed in VERIFICATION) confirm the conjectured threshold holds for those cases.

(ii) First gap (crisp): Prove that if $e(G)\ge \frac{k-1}{2}n+1$ then $G$ contains every tree on $k+1$ vertices (not just stars), i.e. bridge the factor-of-two gap between $n(k-1)+1$ and $\frac{k-1}{2}n+1$.

(iii) Top 3 next moves: 1. Inductive reduction on $n$: Show that if $G$ has a vertex of degree $\le \frac{k-1}{2}$ then deleting it preserves the edge threshold and reduces to a smaller instance; hence a minimal counterexample must satisfy $\delta(G)\ge \lfloor\frac{k-1}{2}\rfloor+1$. 2. Minimum-degree embedding: Prove that graphs satisfying $e(G)\ge \frac{k-1}{2}n+1$ and $\delta(G)\ge \lfloor\frac{k-1}{2}\rfloor+1$ necessarily contain every $(k+1)$-vertex tree, perhaps via a refined greedy embedding that uses only the available degree slack. 3. Computer-aided search for small counterexamples for fixed $k$: For each small $k$ (say $k\le 6$), enumerate graphs at the threshold and test containment of all $(k+1)$-vertex trees to see whether the conjecture ever fails at small sizes.

(iv) Minimal counterexample structure: A minimal counterexample would consist of a graph $G$ on $n\ge k+1$ vertices with $e(G)=\lceil\frac{k-1}{2}n\rceil+1$ that avoids some specific tree $T$ on $k+1$ vertices; by the inductive reduction in (iii).1, it should have minimum degree at least $\lfloor\frac{k-1}{2}\rfloor+1$.