Problem 718

Is there some constant $C>0$ such that any graph on $n$ vertices with $\geq Cr^2n$ edges contains a subdivision of $K_r$ ?

Source: erdosproblems.com/718

Graph theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved is the site's label, and the answer is yes. The theorem is stated first-hand in Bollobás and Thomason's own proof paper [BT98] (European J. Combin. 19 (1998), 883--887; printed p. 886, PDF p. 4 of the publisher's open-archive PDF), which is not one of the two papers the site names (its key for their proof, BoTh96, is Highly linked graphs), paged at Theorem 4 (Bollobás and Thomason 1998): "Let $p$ be a positive integer and let $G$ be a graph of size $256p^2|G|$ . Then $G$ contains a topological subgraph of order $p$ ", where $|G|$ is the order, the size is the number of edges, and a topological complete graph of order $p$ has $p$ vertices joined pairwise by vertex-disjoint paths (p. 883); the abstract states it with "at least $256p^2|G|$ " and calls the result the proof of "a conjecture made by Mader and by Erdös and Hajnal". With $p=r$ this is the site's statement with $C=256$ . The other proof, Komlós and Szemerédi's [KoSz96], is not held in its own text. The two claim pages, Bollobás and Thomason and Komlós and Szemerédi, record the two results, their scope and their acceptance evidence, from which the frontmatter standing is derived. The theorem is also quoted in a refereed paper: Theorem 3.1 (Fox 2013) of Fox, Lee and Sudakov [FLS13] (Combinatorica 33 (2013), 181--197; p. 4 of arXiv v3): "Every graph $G$ with $n$ vertices and at least $256t^2n$ edges satisfies $\sigma(G)\ge t$ ", stated as "a theorem independently proved by Bollobás and Thomason [5], and Komlós and Szemerédi [13]" that solved "an old conjecture made by Erdős and Hajnal, and also by Mader". This is the attestation shape: the statement is first-hand in a refereed proof paper, whose proof is followed here at filing depth only, and the second proof is second-hand. Mader's earlier bound is stated in his own text: Satz 2 of [Ma67] (Math. Ann. 174 (1967), 265--268; printed p. 266), paged at Satz 2, gives a subdivision of $K_r$ in every finite graph with $n$ vertices and at least $2^{\binom{r-1}2-1}(r-1)n$ edges, a constant smaller than the $2^{\binom r2}$ in which Erdős's 1981 paper and the site quote the bound, so the quoted form follows from it. A site-versus-source item on the key BoTh96 is recorded below.

BT98: Bollobás, B. and Thomason, A., Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs. European J. Combin. 19 (1998), no. 8, 883--887, doi:10.1006/eujc.1997.0188 (November 1998; Crossref record accessed 2026-09-19, whose license field carries the publisher's open-archive license dated 2013; OpenAlex lists it as open at the DOI). The publisher's open-archive PDF has 5 pages, printed pp. 883--887 ("Received 15 March 1997 and accepted 9 September 1997", p. 887). Printed p. 886 (PDF p. 4): Theorem 4, quoted under Status. The paper [FLS13] cites for the theorem (its [5]); not a site key. Library home: Bollobás and Thomason 1998; paged at Bollobás and Thomason 1998, Theorem 4.
BoTh96: Bollobás, Béla and Thomason, Andrew, Highly linked graphs. Combinatorica 16 (1996), no. 3, 313--320, doi:10.1007/BF01261316 (September 1996; Crossref record accessed). The site's key; not held. [BT98] (p. 886) names it, as its reference [3], as the paper where the stronger result that "a graph $G$ of size $22k|G|$ contains a $k$ -linked subgraph" would appear, a result that "implies the truth of the conjecture with a constant smaller than 256"; whether it also states the theorem was not checked.
KoSz96: Komlós, János and Szemerédi, Endre, Topological cliques in graphs. II. Combin. Probab. Comput. 5 (1996), no. 1, 79--90, doi:10.1017/S096354830000184X (March 1996; Crossref record accessed). Not held; its abstract, on the publisher's page, says "This note contains a refinement of our paper [8], leading to an alternative proof of a conjecture of Mader and of Erdős and Hajnal recently proved by Bollobás and Thomason." [BT98] (p. 883) says of it, as its reference [9], that Komlós and Szemerédi completed the refinement of their own method very shortly after [BT98] was written, "so obtaining an alternative proof of the conjecture".
Ma67: Mader, W., Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Math. Ann. 174 (1967), no. 4, 265--268, doi:10.1007/BF01364272 (Crossref record accessed). The printed article has 4 pages, pp. 265--268 ("Eingegangen am 2. Juni 1966", p. 268). Printed p. 266: Satz 2, quoted under the Current assessment; the paper writes $e(G)$ for the number of vertices and $k(G)$ for the number of edges. Library home: Mader 1967; paged at Mader 1967, Satz 2.
Di60: Dirac, Gabriel Andrew, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen. Math. Nachr. 22 (1960), no. 1--2, 61--85, doi:10.1002/mana.19600220107 (Crossref record accessed). The printed article has 25 pages, pp. 61--85 ("Eingegangen am 12. 10. 1959", p. 61). Printed p. 68: Satz 6, the $2N-2$ theorem with the hypotheses finite and $N\ge4$ , and the sentence that the graphs of Figures 3--5 (p. 67) show it best possible; the paper writes $\{4\}$ for a complete 4-graph and $\{4U\}$ for a subdivision of one. Library home: Dirac 1960; paged at Dirac 1960, Satz 6.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42, doi:10.1007/BF02579174 (Crossref record accessed); Part IV, item 2, p. 8 of the retyped copy, which has its own pagination. Library home: Erdős 1981.
FLS13: Fox, Jacob and Lee, Choongbum and Sudakov, Benny, Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz. Combinatorica 33 (2013), no. 2, 181--197, doi:10.1007/s00493-013-2853-x; pagination from arXiv:1107.1920v3 (14 February 2012): Theorem 3.1 on p. 4 and the average-degree form on p. 1. Not a site key for this problem. Library home: Fox 2013; paged at Fox 2013, Theorem 3.1 (Bollobás–Thomason, Komlós–Szemerédi, as quoted).
ErHa69: Erdős, P. and Hajnal, A., On complete topological subgraphs of certain graphs. Ann. Univ. Sci. Budapest 7 (1969), 193--199, as [Er81] cites it ("See Erdős--Hajnal [26]"). Not held; cited here for the origin of the conjecture only.

Problem 718

Status

Proof claims

Discussion