Problem 1018

Let $\epsilon>0$ . Is there a constant $C_\epsilon$ such that, for all large $n$ , every graph on $n$ vertices with at least $n^{1+\epsilon}$ edges must contain a subgraph on at most $C_\epsilon$ vertices which is non-planar?

Source: erdosproblems.com/1018

Graph theory
Planar graphs

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Solved (the site's label SOLVED; on 2026-10-07 the page printed no label, and the community database listed the problem as solved (Lean), with a last update of 16 September 2026). The answer is yes: Kostochka and Pyber (Combinatorica 8 (1988), no. 1, 83--86; refereed) state Erdős's question in their introduction and answer it with their Theorem (p. 83): "Every $G[n,4^{t^2}n^{1+\varepsilon}]$ contains a $TK_t$ of size at most $c(\varepsilon,t)\le7t^2\log t/\varepsilon$ for all $t\in\mathbb N$ and $\varepsilon>0$ ", where $G[n,m]$ is a graph with $n$ vertices and $m$ edges and $TK_t$ a topological complete graph (a subdivided $K_t$ ) of $t$ vertices; "This result answers the question of Erdős" (p. 83). Library home: Kostochka and Pyber 1988, result page Theorem. With $t=5$ this gives a non-planar subgraph on $O(1/\epsilon)$ vertices in every graph with $n^{1+\epsilon}$ edges once $n$ is large (an authored conversion below); the site's account and the restatement in Janzer's refereed paper of 2021 (Bull. London Math. Soc. 53, 108--118; quoted from its arXiv copy) agree with the printed statement. The label rests on Erdős's question, the site's acceptance and the Theorem as printed; the proof (p. 85) was followed for structure and not checked. The claim page Kostochka and Pyber records the result, its acceptance evidence and its postings, and the standing derives from it: the question is answered in the affirmative, so the claim's value is proved, while this sentence keeps the site's label. Jiang (J. Graph Theory 67 (2011), 139--152; not held) later sharpened the bound, as Janzer reports.

Er71: Erdős, P., Some unsolved problems in graph theory and combinatorial analysis. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97--109; item 12, p. 102. Library home: Erdős 1971 (a scan); the passage is paged at Erdős 1971, Item 12 (p. 102).
KoPy88: Kostochka, A. and Pyber, L., Small topological complete subgraphs of "dense" graphs. Combinatorica 8 (1988), no. 1, 83--86, doi:10.1007/BF02122555 (received October 2, 1985, revised September 15, 1986, per p. 83; Crossref record). Erdős's question, the Theorem, the Remark and the Notation, p. 83; the lemmas, p. 84; the proof and the note added in proof, p. 85. Library home: Kostochka and Pyber 1988; the theorem is paged at Kostochka and Pyber 1988, Theorem.
Ja21: Janzer, O., The extremal number of longer subdivisions. Bull. London Math. Soc. 53 (2021), 108--118, doi:10.1112/blms.12404; arXiv:1905.08001v1 (20 May 2019, 11 pages; the arXiv record carries the journal reference). Its arXiv copy is the version cited here, for its introduction (p. 1). Library home: Janzer 2021. The thread's pointer.
Ji11: Jiang, T., Compact topological minors in graphs. J. Graph Theory 67 (2011), no. 2, 139--152, doi:10.1002/jgt.20522 (Crossref record). Not held; its theorem is quoted from [Ja21], p. 1.
FLS13: Fox, J., Lee, C. and Sudakov, B., Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős--Fajtlowicz. Combinatorica 33 (2013), 181--197. Library home: Fox 2013 (arXiv:1107.1920v3). Carries no quotation of [KoPy88]: its introduction cites the Bollobás--Thomason and Komlós--Szemerédi theorem that average degree $d$ forces a clique subdivision of order $c\sqrt d$ , whose subdivision is not of bounded order; not used on this page.

Problem 1018

Status

Proof claims

Discussion