Conjectured by Faber, Lovász, and Erdős (apparently 'at a party in Boulder, Colarado in September 1972' [Er81]).

Kahn [Ka92] proved that $\chi(G)\leq (1+o(1))n$ (for which Erdős gave him a 'consolation prize' of \$100). Hindman has proved the conjecture for $n<10$. Kang, Kelly, Kühn, Methuku, and Osthus [KKKMO21] have proved the answer is yes for all sufficiently large $n$.

In [Er97d] Erdős asks how large $\chi(G)$ can be if instead of asking for the copies of $K_n$ to be edge disjoint we only ask for their intersections to be triangle free, or to contain at most one edge.

In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that (for sufficiently large $n$) \[\mathrm{rt}(n; 4,\epsilon n)\geq n^2/8?\]

Conjectured by Bollobás and Erdős [BoEr76], who proved the existence of such a graph with $(1/8+o(1))n^2$ many edges. Solved by Fox, Loh, and Zhao [FLZ15], who proved that for every $n\geq 1$ there exists a graph on $n$ vertices with $\geq n^2/8$ many edges, containing no $K_4$, whose largest independent set has size at most \[ \ll \frac{(\log\log n)^{3/2}}{(\log n)^{1/2}}n.\]

See also [615].

The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky [BCL21], who proved that deleting at most $1.064n^2$ edges suffices.

In [Er92b] Erdős asks, more generally, if a graph on $(2k+1)n$ vertices in which every odd cycle has size $\geq 2k+1$ can be made bipartite by deleting at most $n^2$ edges.

See also the entry in the graphs problem collection.

Győri proved this with $1.03n^5$, which has been improved by Füredi. The answer is yes, as proved independently by Grzesik [Gr12] and Hatami, Hladky, Král, Norine, and Razborov [HHKNR13].

In [Er92b] and [Er97f] Erdős asks more generally: if $r\geq 5$ is odd and a graph has $rn$ vertices and the smallest odd cycle has size $r$ then is the number of cycles of size $r$ at most $n^{r}$?

Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20]. In [Er81] Erdős asks whether the $a_i$ must in fact have positive upper density, and in [Er95d] he speculates the upper density (or even upper logarithmic density) must be $\geq 1/2$.

The lower density of the set can be $0$ since there are graphs of arbitrarily large chromatic number and girth.

See also [65].

Conjectured by Bollobás and Erdős. Bollobás and Shelah have confirmed this for $k=1$. Proved by Gyárfás [Gy92], who proved the stronger result that, if $G$ is 2-connected, then $G$ is either $K_{2k+2}$ or contains a vertex of degree at most $2k$.

A stronger form was established by Gao, Huo, and Ma [GaHuMa21], who proved that if a graph $G$ has chromatic number $\chi(G)\geq 2k+3$ then $G$ contains cycles of $k+1$ consecutive odd lengths.

If $G$ is not bipartite the answer is yes, proved by Erdős, Frankl, and Rödl [ErFrRo86]. The answer is no for $G=C_6$, the cycle on 6 vertices. Morris and Saxton [MoSa16] have proved there are at least \[2^{(1+c)\mathrm{ex}(n;C_6)}\] such graphs for infinitely many $n$, for some constant $c>0$. It is still possible (and conjectured by Morris and Saxton) that the weaker bound of \[2^{O(\mathrm{ex}(n;G))}\] holds for all $G$.

Conjectured by Erdős and Simonovits, who could not even prove that at least $2$ copies of $C_4$ are guaranteed.

He, Ma, and Yang [HeMaYa21] have proved this conjecture when $n=q^2+q+1$ for some even integer $q$.

Conjectured by Erdős and Hajnal [ErHa89], who proved that a complete graph or independent set must exist on \[\geq \exp(c_H\sqrt{\log n})\] many vertices, where $c_H>0$ is some constant. This was improved by Bucić, Nguyen, Scott, and Seymour [BNSS23] to \[\geq \exp(c_H\sqrt{\log n\log\log n}).\]

See also the entry in the graphs problem collection.

Erdős also asked [Er87] about finding a common subgraph $H$ (with chromatic number either $4$ or $\aleph_0$) in any finite collection of graphs with chromatic number $\aleph_1$.

Every graph with chromatic number $\aleph_1$ contains all sufficiently large odd cycles (which have chromatic number $3$), see [594]. This was proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that 'probably' every graph with chromatic number $\aleph_1$ contains as subgraphs all graphs with chromatic number $4$ with sufficiently large girth.

Conjectured by Mihók and Erdős. It is likely that $2^n$ can be replaced by any sufficiently quickly growing sequence (e.g. the squares).

David Penman has observed that this is certainly true if the graph has uncountable chromatic number, since by a result of Erdős and Hajnal [ErHa66] such a graph must contain arbitrarily large finite complete bipartite graphs (see also Theorem 3.17 of Reiher [Re24]).

Zach Hunter has observed that this follows from the work of Liu and Montgomery [LiMo20]: if $G$ has infinite chromatic number then, for infinitely many $r$, it must contain some finite connected subgraph $G_r$ with chromatic number $r$ (via the de Bruijn-Erdős theorem [dBEr51]). Each $G_r$ contains some subgraph $H_r$ with minimum degree at least $r-1$, and hence via Theorem 1.1 of [LiMo20] there exists some $\ell_r\geq r^{1-o(1)}$ such that $H_r$ contains a cycle of every even length in $[(\log \ell)^8,\ell]$.

See also [64].

Conjectured by Erdős and Gyárfás, who believed the answer must be negative, and in fact for every $r$ there must be a graph of minimum degree at least $r$ without a cycle of length $2^k$ for any $k\geq 2$.

This was solved in the affirmative if the minimum degree is larger than some absolute constant by Liu and Montgomery [LiMo20] (therefore disproving the above stronger conjecture of Erdős and Gyárfás). Liu and Montgomery prove a much stronger result: if the average degree of $G$ is sufficiently large then there is some large integer $\ell$ such that for every even integer $m\in [(\log \ell)^8,\ell]$, $G$ contains a cycle of length $m$.

An infinite tree with minimum degree $3$ shows that the answer is trivially false for infinite graphs.

See also the entry in the graphs problem collection.

A problem of Erdős and Hajnal. Gyárfás, Komlós, and Szemerédi [GyKoSz84] have proved that this sum is $\gg \log k$. Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$.

See also the entry in the graphs problem collection.

See also [57].

Erdős and Rado proved that $\mathfrak{c}\to (\omega+n,4)_2^3$ for any $2\leq n<\omega$.

In [Er82e] Erdős credits this conjecture to himself and Burr. This has been proved by Bollobás [Bo77]. The best dependence of the constant $c(P)$ is unknown.

See also [72].

Bollobás [Bo77] proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers (see [71]).

Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although he conjectured that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

See also the entry in the graphs problem collection.

Proved by Reed [Re99]. (Thanks also to Reed for pointing out that the case $k=0$ is trivial, since if $G$ is not bipartite then $G$ contains an odd cycle.)

See also [922] and the entry in the graphs problem collection.

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82].

Rödl [Ro82] has proved this for hypergraphs, and also proved there is such a graph (with chromatic number $\aleph_0$) if $f(n)=\epsilon n$ for any fixed constant $\epsilon>0$.

It is open even for $f(n)=\sqrt{n}$. Erdős offered \$500 for a proof but only \$250 for a counterexample. This fails (even with $f(n)\gg n$) if the graph has chromatic number $\aleph_1$ (see [111]).

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. In [Er95d] Erdős suggests this may even be true with an independent set of size $\gg n$.

See also [750].

Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c>1/24$.

Erdős offered \$100 for just a proof of the existence of this constant, without determining its value. He also offered \$1000 for a proof that the limit does not exist, but says 'this is really a joke as [it] certainly exists'. Erdős proved \[\sqrt{2}\leq \liminf_{k\to \infty}R(k)^{1/k}\leq \limsup_{k\to \infty}R(k)^{1/k}\leq 4.\] The upper bound has been improved to $4-\tfrac{1}{128}$ by Campos, Griffiths, Morris, and Sahasrabudhe [CGMS23]. This was improved to $3.7992\cdots$ by Gupta, Ndiaye, Norin, and Wei [GNNW24].

A shorter and simpler proof of an upper bound of the strength $4-c$ for some constant $c>0$ (and a generalisation to the case of more than two colours) was given by Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba [BBCGHMST24].

This problem is #3 in Ramsey Theory in the graphs problem collection.

Erdős gave a simple probabilistic proof that $R(k) \gg k2^{k/2}$. Equivalently, this question asks for an explicit construction of a graph on $n$ vertices which does not contain any clique or independent set of size $\geq c\log n$ for some constant $c>0$.

In [Er69b] Erdős asks for even a construction whose largest clique or independent set has size $o(n^{1/2})$, which is now known.

Cohen [Co15] (see the introduction for further history) constructed a graph on $n$ vertices which does not contain any clique or independent set of size \[\geq 2^{(\log\log n)^{C}}\] for some constant $C>0$. Li [Li23b] has recently improved this to \[\geq (\log n)^{C}\] for some constant $C>0$.

This problem is #4 in Ramsey Theory in the graphs problem collection.

Asked by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. $K_4$ is the only known example of such a graph.

Wigderson [Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown.)

A problem of Erdős and Rothschild. Alon and Trotter showed that, provided $c<1/4$, $f_c(n)\ll_c n^{1/2}$. Szemerédi observed that his regularity lemma implies that $f_c(n)\to \infty$.

Edwards (unpublished) and Khadziivanov and Nikiforov [KhNi79] proved independently that $f_c(n) \geq n/6$ when $c>1/4$ (see [905]).

Fox and Loh [FoLo12] proved that \[f_c(n) \leq n^{O(1/\log\log n)}\] for all $c<1/4$, disproving the first conjecture of Erdős.

The best known lower bounds for $f_c(n)$ are those from Szemerédi's regularity lemma, and as such remain very poor.

See also [600] and the entry in the graphs problem collection.

Asked by Erdős, Ordman, and Zalcstein [EOZ93], who proved an upper bound of $(1/4-\epsilon)n^2$ many cliques (for some very small $\epsilon>0$). The example of all edges between a complete graph on $n/3$ vertices and an empty graph on $2n/3$ vertices show that $n^2/6+O(n)$ is sometimes necessary.

A split graph is one where the vertices can be split into a clique and an independent set. Every split graph is chordal. Chen, Erdős, and Ordman [CEO94] have shown that any split graph can be partitioned into $\frac{3}{16}n^2+O(n)$ many cliques.

Conjectured by Erdős, Fajtlowicz, and Stanton. It is known that $F(5)=3$ and $F(7)=4$. Ramsey's theorem implies that $F(n)\gg \log n$. Bollobás observed that $F(n)\ll n^{1/2+o(1)}$. Alon, Krivelevich, and Sudakov [AKS07] have improved this to $n^{1/2}(\log n)^{O(1)}$.

Conjectured by Erdős and Faudree, who showed that $2^{n/2}<f(n) \leq 2^{n-2}$. The first problem was solved by Verstraëte [Ve04], who proved \[f(n)\ll 2^{n-n^{1/10}}.\] This was improved by Nenadov [Ne25] to \[f(n) \ll 2^{n-n^{1/2-o(1)}}.\]

One can also ask about the existence and value of $\lim f(n)^{1/n}$.

A weaker version of the conjecture asks for some constant $c$ such that $f(m)>f(n)-c$ for all $m>n$. This question can be asked for other graphs than $C_4$.

The best known result is due to Balogh, Hu, Lidicky, and Liu [BHLL14], who proved that $0.6068 n2^{n-1}$ edges suffice. Erdős [Er91] observes that there exist subgraphs with \[\geq \left(\frac{1}{2}+\frac{c}{n}\right)n2^{n-1}\] many edges without a $C_4$ (for some constant $c>0$). He suggests that it is 'perhaps not hopeless' to determine the threshold exactly.

A similar question can be asked for other even cycles.

See also [666] and the entry in the graphs problem collection.

Erdős originally conjectured that $R(G)\geq R(k)$, which is trivial for $k=3$, but fails already for $k=4$, as Faudree and McKay [FaMc93] showed that $R(W)=17$ for the pentagonal wheel $W$.

Since $R(k)\leq 4^k$ this is trivial for $\epsilon\geq 3/4$. Yuval Wigderson points out that $R(G)\gg 2^{k/2}$ for any $G$ with chromatic number $k$ (via a random colouring), which asymptotically matches the best-known lower bounds for $R(k)$.

This problem is #12 and #13 in Ramsey Theory in the graphs problem collection.

Conjectured by Erdős and McKay, who proved it with $\delta n^2$ replaced by $\delta (\log n)^2$. Solved by Kwan, Sah, Sauermann, and Sawhney [KSSS22]. Erdős' original formulation also had the condition that $G$ has $\gg n^2$ edges, but an old result of Erdős and Szemerédi says that this follows from the other condition anyway.

Conjectured by Erdős and Hajnal. Rödl [Ro77] has proved the $r=4$ case (see [923]). The infinite version (whether every graph of infinite chromatic number contains a subgraph of infinite chromatic number whose girth is $>k$) is also open.

In [Er79b] Erdős also asks whether \[\lim_{k\to \infty}\frac{f(k,r+1)}{f(k,r)}=\infty.\]

See also the entry in the graphs problem collection and [740] for the infinitary version.

Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. This fails if the graph has chromatic number $\aleph_0$.

A theorem of de Bruijn and Erdős [dBEr51] implies that, if $G$ has infinite chromatic number, then $G$ has a finite subgraph of chromatic number $n$ for every $n\geq 1$.

In [Er95d] Erdős suggests this is true, although such an $F$ must grow faster than the $k$-fold iterated exponential function for any $k$.

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Every $G$ with chromatic number $\aleph_1$ must have $h_G(n)\gg n$ since $G$ must contain, for some $r$, $\aleph_1$ many vertex disjoint odd cycles of length $2r+1$.

On the other hand, Erdős, Hajnal, and Szemerédi proved that there is a $G$ with chromatic number $\aleph_1$ such that $h_G(n)\ll n^{3/2}$. In [Er81] Erdős conjectured that this can be improved to $\ll n^{1+\epsilon}$ for every $\epsilon>0$.

See also [74].

A problem of Erdős and Rado [ErRa67], who showed $k(n,m) \ll_m n^{m-1}$, or more precisely, \[k(n,m) \leq \frac{2^{m-1}(n-1)^m+n-2}{2n-3}.\] Larson and Mitchell [LaMi97] improved the dependence on $m$, establishing in particular that $k(n,3)\leq n^{2}$. Zach Hunter has observed that \[R(n,m) \leq k(n,m)\leq R(n,m,m),\] which in particular proves the upper bound $k(n,m)\leq 3^{n+2m}$.

See also the entry in the graphs problem collection - on this site the problem replaces transitive tournament with directed path, but Zach Hunter and Raphael Steiner have a simple argument that proves, for this alternative definition, that $k(n,m)=(n-1)(m-1)$.

Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered \$250 for a proof and \$100 for a counterexample, but in [Er93] offered \$500 for a counterexample.

Disproved by Janzer [Ja21] who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [146] and [147] and the entry in the graphs problem collection.

Conjectured by Erdős, Kohayakava, and Gyárfás. Edwards [Ed73] proved that $f(m)\geq 0$ always. Note that $f(\binom{n}{2})= 0$, taking $K_n$. Solved by Alon [Al96], who showed $f(n^2/2)\gg n^{1/2}$, and also showed that $f(m)\ll m^{1/4}$ for all $m$. The best possible constant in $f(m)\leq Cm^{1/4}$ is unknown.

A problem of Erdős and Rousseau. The constant $50$ would be best possible as witnessed by a blow-up of $C_5$ or the Petersen graph. Krivelevich [Kr95] has proved this with $n/2$ replaced by $3n/5$ (and $50$ replaced by $25$).

Keevash and Sudakov [KeSu06] have proved this under the additional assumption that $G$ has at most $n^2/12$ edges.

See also the entry in the graphs problem collection.

Conjectured by Erdős and Gyárfás, who proved the existence of some $C>1$ such that $R(n;3,r)>C^{\sqrt{n}}$. Note that when $r=k=2$ we recover the classic Ramsey numbers. Erdős thought it likely that for all $r,k\geq 2$ there exists some $C_1,C_2>1$ (depending only on $r$) such that \[ C_1^{n^{1/k-1}}< R(n;k,r) < C_2^{n^{1/k-1}}.\] Antonio Girao has pointed out that this problem as written is easily disproved, and indeed $R(n;3,2) \geq C^{n}$:

The obvious probabilistic construction (randomly colour the edges red/blue independently uniformly at random) yields a 2-colouring of the edges of $K_N$ such every set on $n$ vertices contains a red triangle and a blue triangle (using that every set of $n$ vertices contains $\gg n^2$ edge-disjoint triangles), provided $N \leq C^n$ for some absolute constant $C>1$. This implies $R(n;3,2) \geq C^{n}$, contradicting the conjecture.

Perhaps Erdős had a different problem in mind, but it is not clear what that might be. It would presumably be one where the natural probabilistic argument would deliver a bound like $C^{\sqrt{n}}$ as Erdős and Gyárfás claim to have achieved via the probabilistic method.

Asked by Andrásfai and Erdős. Erdős [Er97b] also asked where such a graph could contain an infinite complete graph, but this is impossible by an earlier result of Anning and Erdős [AnEr45].

See also [213].

Asked by Erdős and Pach. The lower bound $f(n)\geq (1-o(1))\sqrt{n}$ follows from the fact that a graph with maximum degree $d$ and diameter $2$ has at most $1+d+d(d-1)=d^2+1$ many vertices.

Simonovits observed that the subsets of $[3m-1]$ of size $m$, two sets joined by edge if and only if they are disjoint, forms a triangle-free graph of diameter $2$ which is regular of degree $\binom{2m-1}{m}$. This construction proves that \[f(n) \leq n^{(1+o(1))\frac{2}{3H(1/3)}}=n^{0.7182\cdots},\] where $H(x)$ is the binary entropy function. In [Er97b] Erdős encouraged the reader to try and find a better construction.

In this note Alon provides a simple construction that proves $f(n) \ll \sqrt{n\log n}$: take a triangle-free graph with independence number $\ll \sqrt{n\log n}$ (the existence of which is the lower bound in [165]) and add edges until it has diameter $2$; the neighbourhood of any set is an independent set and hence the maximum degree is still $\ll \sqrt{n\log n}$.

Hanson and Seyffarth [HaSe84] proved that $f(n)\leq (\sqrt{2}+o(1))\sqrt{n}$ using a Cayley graph on $\mathbb{Z}/n\mathbb{Z}$, with the generating set given by some symmetric complete sum-free set of size $\sim \sqrt{n}$. An alternative construction of such a complete sum-free set was given by Haviv and Levy [HaLe18].

Füredi and Seress [FuSe94] proved that $f(n)\leq (\frac{2}{\sqrt{3}}+o(1))\sqrt{n}$.

The precise asymptotics of $f(n)$ are unknown; Alon believes that the truth is $f(n)\sim \sqrt{n}$.

Asked by Erdős and Gyárfás, who proved that this is the case when $G$ has maximum degree $\ll \log n/\log\log n$. A construction of Simonovits shows that this conjecture is false if we just have maximum degree $\leq Cn^{1/2}$, for some large enough $C$.

In this note Alon solves this problem in a strong form, in particular proving that a triangle-free graph on $n$ vertices with maximum degree $<n^{1/2-\epsilon}$ can be made into a triangle-free graph with diameter $2$ by adding at most $O(n^{2-\epsilon})$ edges.

See also [618].

Asked by Erdős and Gyárfás, who proved that \[\frac{5}{6}(n-1) < f(n)<n,\] and that $f(9)=8$. Erdős believed the upper bound is closer to the truth. In fact the lower bound is: Bennett, Cushman, Dudek,and Pralat [BCDP22] have shown that \[f(n) \sim \frac{5}{6}n.\] Joos and Mubayi [JoMu22] have found a shorter proof of this.

Conjectured by Erdős and Simonovits [ErSi84]. Open even for $r=2$. Alon, Krivelevich, and Sudakov [AKS03] have proved \[\mathrm{ex}(n;H) \ll n^{2-1/4r}.\] They also prove the full Erdős-Simonovits conjectured bound if $H$ is bipartite and the maximum degree in one component is $r$.

See also [113] and [147].

See also the entry in the graphs problem collection.

Conjectured by Erdős and Simonovits [ErSi84]. Disproved by Janzer [Ja21], who constructed, for any $\epsilon>0$, a $3$-regular bipartite graph $H$ such that \[\mathrm{ex}(n;H)\ll n^{\frac{4}{3}+\epsilon}.\]

See also [113], [146], and [714].

See also the entry in the graphs problem collection.

Asked by Erdős and Nešetřil in 1985 (see [FGST89]). This bound would be the best possible, as witnessed by a blowup of $C_5$. The minimum number of such sets required is sometimes called the strong chromatic index of $G$.

The weaker conjecture that there exists some $c>0$ such that $(2-c)\Delta^2$ sets suffice was proved by Molloy and Reed [MoRe97], who proved that $1.998\Delta^2$ sets suffice (for $\Delta$ sufficiently large). This was improved to $1.93\Delta^2$ by Bruhn and Joos [BrJo18] and to $1.835\Delta^2$ by Bonamy, Perrett, and Postle [BPP22]. The best bound currently available is \[1.772\Delta^2,\] proved by Hurley, de Joannis de Verclos, and Kang [HJK22].

Erdős and Nešetřil also asked the easier problem of whether $G$ containing at least $\tfrac{5}{4}\Delta^2$ many edges implies $G$ containing two strongly independent edges. This was proved independently by Chung-Trotter and Gyárfás-Tuza.

Asked by Erdős and Nešetřil, who also ask whether $c(3m+2)=3^m$. Seymour observed that $c(3m+2)\geq 3^m$, as seen by the graph of $m$ independent paths of length $4$ joining two vertices.

Solved by Bradač [Br24], who proved that $\alpha=\lim c(n)^{1/n}$ exists and \[\alpha \leq 2^{H(1/3)}=1.8899\cdots,\] where $H(\cdot)$ is the binary entropy function. Seymour's construction proves that $\alpha\geq 3^{1/3}=1.442\cdots$. Bradač conjectures that this lower bound is the true value of $\alpha$.

It is easy to see that $h(n)\leq n-\sqrt{n}$ and that $h(n)\leq n-H(n)$. Conjectured by Erdős and Gallai, who were unable to make progress even assuming $G$ is $K_4$-free. Erdős remarked that this conjecture is 'perhaps completely wrongheaded'.

The current bounds are \[ \frac{n^{3/2}}{(\log n)^{3/2}}\ll R(C_4,K_n)\ll \frac{n^2}{(\log n)^2}.\] The upper bound is due to Szemerédi (mentioned in [EFRS78]), and the lower bound is due to Spencer [Sp77].

This problem is #17 in Ramsey Theory in the graphs problem collection.

The Burr-Erdős conjecture. This is equivalent to showing that if $H$ is the union of $c$ forests then $R(H)\ll_c n$, and also that if every subgraph has average degree at most $d$ then $R(H)\ll_d n$. Solved by Lee [Le16], who proved that \[ R(H) \leq 2^{2^{O(d)}}n.\]

This problem is #9 in Ramsey Theory in the graphs problem collection. See also [800].

It is known that there exists some constant $c>0$ such that for large $k$ \[c\frac{k^2}{\log k}\leq R(3,k) \leq (1+o(1))\frac{k^2}{\log k}.\] The lower bound is due to Kim [Ki95], the upper bound is due to Shearer [Sh83], improving an earlier bound of Ajtai, Komlós, and Szemerédi [AjKoSz80]. The lower bound has been improved to \[\left(\frac{1}{4}-o(1)\right)\frac{k^2}{\log k}\] independently by Bohman and Keevash [BoKe21] and Pontiveros, Griffiths and Morris [PGM20]. The latter collection of authors conjecture that this lower bound is the true order of magnitude.

See also [544].

Spencer [Sp77] proved \[R(4,k) \gg (k\log k)^{5/2}.\] Ajtai, Komlós, and Szemerédi [AKS80] proved \[R(4,k) \ll \frac{k^3}{(\log k)^2}.\] This is true, and was proved by Mattheus and Verstraete [MaVe23], who showed that \[R(4,k) \gg \frac{k^3}{(\log k)^4}.\]

This problem is #5 in Ramsey Theory in the graphs problem collection.

A problem of Tuza. It is trivial that $G$ can be made triangle-free after removing at most $3k$ edges. The examples of $K_4$ and $K_5$ show that $2k$ would be best possible.

A problem of Erdős and Simonovits.

This is trivially true if $\mathcal{F}$ does not contain any bipartite graphs, since by the Erdős-Stone theorem if $H\in\mathcal{F}$ has minimal chromatic number $r\geq 2$ then \[\mathrm{ex}(n;H)=\mathrm{ex}(n;\mathcal{F})=\left(\frac{r-2}{r-1}+o(1)\right)\binom{n}{2}.\] Erdős and Simonovits observe that this is false for infinite families $\mathcal{F}$, e.g. the family of all cycles.

See also [575] and the entry in the graphs problem collection.

Conjectured by Burr and Erdős. The trivial bound is \[R(Q_n) \leq R(K_{2^n})\leq C^{2^n}\] for some constant $C>1$. This was improved a number of times; the current best bound due to Tikhomirov [Ti22] is \[R(Q_n)\ll 2^{(2-c)n}\] for some small constant $c>0$. (In fact $c\approx 0.03656$ is permissible.)

See also the entry in the graphs problem collection.

Asked by Erdős and Sauer. Resolved by Janzer and Sudakov [JaSu22], who proved that there exists some $C=C(k)>0$ such that any graph on $n$ vertices with at least $Cn\log\log n$ edges contains a $k$-regular subgraph.

A construction due to Pyber, Rödl, and Szemerédi [PRS95] shows that this is best possible.

Erdős offers \$100 for showing that this limit is finite. An easy pigeonhole argument shows that \[R(3;k)\leq 2+k(R(3;k-1)-1),\] from which $R(3;k)\leq \lceil e k!\rceil$ immediately follows. The best-known upper bounds are all of the form $ck!+O(1)$, and arise from this type of inductive relationship and computational bounds for $R(3;k)$ for small $k$. The best-known lower bound (coming from lower bounds for Schur numbers) is due to Exoo [Ex94], \[R(3;k) \gg (321)^{k/5}.\]

See also [483].

See also the entry in the graphs problem collection.

Conjectured by Erdős and Gallai, who proved that $O(n\log n)$ many cycles and edges suffices.

The best bound available is due to Bucić and Montgomery [BM22], who prove that $O(n\log^*n)$ many cycles and edges suffice, where $\log^*$ is the iterated logarithm function.

Conlon, Fox, and Sudakov [CFS14] proved that $O_\epsilon(n)$ cycles and edges suffice if $G$ has minimum degree at least $\epsilon n$, for any $\epsilon>0$.

See also [583].

A problem of Erdős and Entringer [EnEr72], who constructed a graph with \[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\] many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with \[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\] many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for such a construction and \$25 for a proof that no such construction is possible.

Bradač and Christoph [BrCh24] have proved the answer is no: if $f(n)$ is the maximum number of unique subgraphs in a graph on $n$ vertices then \[f(n) = o\left(\frac{2^{\binom{n}{2}}}{n!}\right).\] (Quantitatively the $o(1)$ in their argument can be taken to be $O(\frac{\log\log\log n}{\log\log n})$.)

A problem of Turán. Turán observed that dividing the vertices into three equal parts $X_1,X_2,X_3$, and taking the edges to be those triples that either have exactly one vertex in each part or two vertices in $X_i$ and one vertex in $X_{i+1}$ (where $X_4=X_1$) shows that \[\mathrm{ex}_3(n,K_4^3)\geq\left(\frac{5}{9}+o(1)\right)\binom{n}{3}.\] This is probably the truth. The current best upper bound is \[\mathrm{ex}_3(n,K_4^3)\leq 0.5611666\binom{n}{3},\] due to Razborov [Ra10].

See also [712] for the general case.

A problem of Erdős and Gyárfás. Gerencsér and Gyárfás [GeGy67] proved that, if the paths do not need to be of the same colour, then two paths suffice. Erdős and Gyárfás [ErGy95] proved that $2\sqrt{n}$ vertices suffice, and observed that $\sqrt{n}$ would be best possible here.

Solved in the affirmative by Pokrovskiy, Versteegen, and Williams [PVW24].

A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, who could prove this is true for $\delta>1/16$, and could further prove it for $\delta>0$ if we replace $K_5$ with $K_4$.

They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620]) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle.

See also [579] and the entry in the graphs problem collection.

This problem is #8 in Ramsey Theory in the graphs problem collection. See also [165].

In other words, are cliques extremal for Ramsey numbers. Asked by Erdős and Graham.

This problem is #10 in Ramsey Theory in the graphs problem collection.

This is true, and was proved by Sudakov [Su11]. The analogous question for $\geq 3$ colours is still open.

Alon, Krivelevich, and Sudakov [AKS03] had earlier given a short proof of this when $G$ is bipartite.

This problem is #11 in Ramsey Theory in the graphs problem collection.

Equality holds when $T$ is a star on $n$ vertices.

Implied by [548].

This problem is #14 in Ramsey Theory in the graphs problem collection.

A problem of Erdős and Sós, who also conjectured that every graph with at least \[\max\left( \binom{2k-1}{2}+1, (k-1)n-(k-1)^2+\binom{k-1}{2}+1\right)\] many edges contains every forest with $k$ edges. (Erdős and Gallai [ErGa59] proved that this is the threshold which guarantees containing $k$ independent edges.)

It can be easily proved by induction that every graph on $n$ vertices with at least $n(k-1)+1$ edges contains every tree on $k+1$ vertices.

Brandt and Dobson [BrDo96] have proved this for graphs of girth at least $5$. Wang, Li, and Liu [WLL00] have proved this for graphs whose complements have girth at least $5$. Saclé and Woznik [SaWo97] have proved this for graphs which contain no cycles of length $4$. Yi and Li [YiLi04] have proved this for graphs whose complements contain no cycles of length $4$.

Implies [547] and [557].

See also the entry in the graphs problem collection.

It follows from results in [EFRS82] that $R(T)\geq 4k-1$.

This is false: Norin, Sun, and Zhao [NSZ16] have proved that if $T$ is the union of two stars on $k$ and $2k$ vertices, with an edge joining the centre of the two stars, then $R(T)\geq (4.2-o(1))k$. The best upper bound for the Ramsey number for this tree is $R(T)\leq 4.27492k+1$, obtained by Dubó and Stein [DuSt24].

This problem is #15 in Ramsey Theory in the graphs problem collection.

Chvátal [Ch77] proved that $R(T,K_m)=(m-1)(n-1)+1$.

This problem is #16 in Ramsey Theory in the graphs problem collection.

Asked by Erdős, Faudree, Rousseau, and Schelp, who also ask for the smallest value of $k$ such that this identity holds (for fixed $n$). They also ask, for fixed $n$, what is the minimum value of $R(C_k,K_n)$?

This identity was proved for $k>n^2-2$ by Bondy and Erdős [BoEr73]. Nikiforov [Ni05] extended this to $k\geq 4n+2$.

Keevash, Long, and Skokan [KLS21] have proved this identity when $k\geq C\frac{\log n}{\log\log n}$ for some constant $C$, thus establishing the conjecture for sufficiently large $n$.

See also the entry in the graphs problem collection.

It was shown in [BEFRS89] that \[ n+\sqrt{n}-6n^{11/40} \leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1.\] Füredi (unpublished) has shown that $R(C_4,S_n)=n+\lceil\sqrt{n}\rceil$ for infinitely many $n$.

See also the entry in the graphs problem collection.

A problem of Erdős and Sós. This was solved by Alon and Rödl [AlRo05], who in fact show that \[R(3,3,n)\asymp n^3(\log n)^{O(1)}\] (recalling that Shearer [Sh83] showed $R(3,n) \ll n^2/\log n$).

See also the entry in the graphs problem collection and [925].

A problem of Erdős and Graham. The problem is open even for $n=2$.

See also the entry in the graphs problem collection.

A problem of Erdős and Graham. Erdős [Er81c] gives the bounds \[k^{1+\frac{1}{2n}}\ll R(C_{2n};k)\ll k^{1+\frac{1}{n-1}}.\] Chung and Graham [ChGr75] showed that \[R(C_4;k)>k^2-k+1\] when $k-1$ is a prime power and \[R(C_4;k)\leq k^2+k+1\] for all $k$.

See also the entry in the graphs problem collection.

A problem of Bondy and Erdős. This inequality is best possible for odd $n$.

Luczak [Lu99] has shown that $R(C_n;3)\leq (4+o(1))n$ for all $n$, and in fact $R(C_n;3)\leq 3n+o(n)$ for even $n$.

Kohayakawa, Simonovits, and Skokan [KSS05] proved this conjecture when $n$ is sufficiently large and odd. Benevides and Skokan [BeSk09] proved that if $n$ is sufficiently large and even then $R(C_n;3)=2n$.

See also the entry in the graphs problem collection.

A problem of Erdős and Graham. Implied by [548].

See also the entry in the graphs problem collection.

Chung and Graham [ChGr75] prove the general bounds \[(2\pi\sqrt{st})^{\frac{1}{s+t}}\left(\frac{s+t}{e^2}\right)k^{\frac{st-1}{s+t}}\leq R(K_{s,t};k)\leq (t-1)(k+k^{1/s})^s\] and determined \[R(K_{2,2},k)=(1+o(1))k^2.\] Alon, Rónyai, and Szabó [ARS99] have proved that \[R(K_{3,3},k)=(1+o(1))k^3\] and that if $s\geq (t-1)!+1$ then \[R(K_{s,t},k)\asymp k^t.\]

See also the entry in the graphs problem collection.

A problem of Beck and Erdős. Beck [Be83b] proved this when $G$ is a path. Friedman and Pippenger [FrPi87] proved this when $G$ is a tree. Haxell, Kohayakawa, and Luczak [HKL95] proved this when $G$ is a cycle. An alternative proof when $G$ is a cycle (with better constants) was given by Javadi, Khoeini, Omidi, and Pokrovskiy [JKOP19].

This was disproved for $d=3$ by Rödl and Szemerédi [RoSz00], who constructed a graph on $n$ vertices with maximum degree $3$ such that \[\hat{R}(G)\gg n(\log n)^{c}\] for some absolute constant $c>0$. Tikhomirov [Ti22b] has improved this to \[\hat{R}(G)\gg n\exp(c\sqrt{\log n}).\] It is an interesting question how large $\hat{R}(G)$ can be if $G$ has maximum degree $3$. Kohayakawa, Rödl, Schacht, and Szemerédi [KRSS11] proved an upper bound of $\leq n^{5/3+o(1)}$ and Conlon, Nenadov, and Trujić [CNT22] proved $\ll n^{8/5}$. The best known upper bound of $\leq n^{3/2+o(1)}$ is due to Draganić and Petrova [DrPe22].

See also the entry in the graphs problem collection.

We know that \[\frac{1}{60}n^22^n<\hat{R}(K_{n,n})< \frac{3}{2}n^32^n.\] The lower bound (which holds for $n\geq 6$) was proved by Erdős and Rousseau [ErRo93]. The upper bound was proved by Erdős, Faudree, Rousseau, and Schelp [EFRS78b] and Nešetřil and Rödl [NeRo78].

Conlon, Fox, and Wigderson [CFW23] have proved that, for any $s\leq t$, \[\hat{R}(K_{s,t})\gg s^{2-\frac{s}{t}}t2^s,\] and prove that when $t\gg s\log s$ we have $\hat{R}(K_{s,t})\asymp s^2t2^s$. They conjecture that this should hold for all $s\leq t$, and so in particular we should have $\hat{R}(K_{n,n})\asymp n^32^n$.

See also the entry in the graphs problem collection.

Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS78] proved this when all the $n_i$ are identical and all the $m_i$ are identical.

See also the entry in the graphs problem collection.

A problem of Erdős, Hajnal, and Rado [EHR65]. A generalisation of [564].

See also the entry in the graphs problem collection.

It is easy to show that, for every $0\leq \alpha\leq 1/2$, \[F(n,\alpha)\asymp_\alpha \log n.\]

Note that when $\alpha=0$ this is just asking for a $2$-colouring of the edges of $K_n$ which contains no monochromatic clique of size $m$, and hence we recover the classical Ramsey numbers.

See also [161].

See also the entry in the graphs problem collection.

A special case of [562]. A problem of Erdős, Hajnal, and Rado [EHR65], who prove the bounds \[2^{cn^2}< R_3(n)< 2^{2^{n}}\] for some constant $c>0$.

Erdős, Hajnal, Máté, and Rado [EHMR84] have proved a doubly exponential lower bound for the corresponding problem with $4$ colours.

See also the entry in the graphs problem collection.

A problem of Erdős and Rödl. Even the existence of $R^*(G)$ is not obvious, but was proved independently by Deuber [De75], Erdős, Hajnal, and Pósa [EHP75], and Rödl [Ro73].

Rödl [Ro73] proved this when $G$ is bipartite. Kohayakawa, Prömel, and Rödl [KPR98] have proved that \[R^*(G) < 2^{O(n(\log n)^2)}.\] An alternative (and more explicit) proof was given by Fox and Sudakov [FoSu08]. Conlon, Fox, and Sudakov [CFS12] have improved this to \[R^*(G) < 2^{O(n\log n)}.\]

See also the entry in the graphs problem collection.

In other words, is $G$ Ramsey size linear? This fails for a graph $G$ with $n$ vertices and $2n-2$ edges (for example with $H=K_n$). Erdős, Faudree, Rousseau, and Schelp [EFRS93] have shown that any graph $G$ with $n$ vertices and at most $n+1$ edges is Ramsey size linear.

Implies [567].

See also the entry in the graphs problem collection.

In other words, is $G$ Ramsey size linear? A special case of [566]. In [Er95] Erdős specifically asks about the case $G=K_{3,3}$.

The graph $H_5$ can also be described as $K_4^*$, obtained from $K_4$ by subdividing one edge. ($K_4$ itself is not Ramsey size linear, since $R(4,n)\gg n^{3-o(1)}$, see [166].) Bradać, Gishboliner, and Sudakov [BGS23] have shown that every subdivision of $K_4$ on at least $6$ vertices is Ramsey size linear, and also that $R(H_5,H) \ll m$ whenever $H$ is a bipartite graph with $m$ edges and no isolated vertices.

See also the entry in the graphs problem collection.

In other words, is $G$ Ramsey size linear?

See also the entry in the graphs problem collection.

See also the entry in the graphs problem collection.

This was proved for even $k$ by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. It was proved for $k=3$ by Sidorenko [Si93].

See also the entry in the graphs problem collection.

A problem of Erdős and Simonovits. Bukh and Conlon [BuCo18] proved the first problem holds if we weaken asking for the extremal number of a single graph to asking for the extremal number of a finite family of graphs.

A rational $\alpha\in [1,2]$ for which the first problem holds is known as a Turán exponent. Known Turán exponents are:

• $\frac{3}{2}-\frac{1}{2s}$ for $s\geq 2$ (Conlon, Janzer, and Lee [CJL21]).
• $\frac{4}{3}-\frac{1}{3s}$ and $\frac{5}{4}-\frac{1}{4s}$ for $s\geq 2$ (Jiang and Qiu [JiQi20]).
• $2-\frac{a}{b}$ for $\lfloor b/a\rfloor^3 \leq a\leq \frac{b}{\lfloor b/a\rfloor+1}+1$ (Jiang, Jiang, and Ma [JJM20]).
• $2-\frac{a}{b}$ with $b>a\geq 1$ and $b\equiv \pm 1\pmod{a}$ (Kang, Kim, and Liu [KKL21]).
• $1+a/b$ with $b>a^2$ (Jiang and Qiu [JiQi23]),
• $2-\frac{2}{2b+1}$ for $b\geq 2$ or $7/5$ (Jiang, Ma, and Yepremyan [JMY22]).
• $2-a/b$ with $b\geq (a-1)^2$ (Conlon and Janzer [CoJa22]).

See also [713] and the entry in the graphs problem collection.

It is easy to see that $\mathrm{ex}(n;C_{2k+1})=\lfloor n^2/4\rfloor$ for any $k\geq 1$ (and $n>2k+1$) (since no bipartite graph contains an odd cycle). Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$.

Erdős [Er64c] and Bondy and Simonovits [BoSi74] showed that \[\mathrm{ex}(n;C_{2k})\ll kn^{1+\frac{1}{k}}.\]

Benson [Be66] has proved this conjecture for $k=3$ and $k=5$. Lazebnik, Ustimenko, and Woldar [LUW95] have shown that, for arbitrary $k\geq 3$, \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{2}{3k-3+\nu}},\] where $\nu=0$ if $k$ is odd and $\nu=1$ if $k$ is even. See [LUW99] for further history and references.

See also [765] and the entry in the graphs problem collection.

A problem of Erdős and Simonovits, who proved that \[\mathrm{ex}(n;\{C_4,C_5\})=(n/2)^{3/2}+O(n).\]

See also [574] and the entry in the graphs problem collection.

A problem of Erdős and Simonovits.

See also [573] and the entry in the graphs problem collection.

A problem of Erdős and Simonovits.

See also [180] and the entry in the graphs problem collection.

Erdős and Simonovits [ErSi70] proved that \[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\] In [Er81] and [Er93] Erdős asked whether it is $\asymp n^{8/5}$.

A theorem of Sudakov and Tomon [SuTo22] implies \[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\] Janzer and Sudakov [JaSu22b] have improved this to \[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\] See also the entry in the graphs problem collection.

A conjecture of Erdős and Faudree. Proved by Wang [Wa10].

A conjecture of Erdős and Bollobás. Solved by Riordan [Ri00], who in fact proved this with any edge-probability $>1/4$, and proves that the number of copies of $Q_d$ is normally distributed.

See also the entry in the graphs problem collection.

A problem of Erdős, Hajnal, Sós, and Szemerédi, who could prove this is true for $\delta>1/8$.

See also [533] and the entry in the graphs problem collection.

A conjecture of Erdős, Füredi, Loebl, and Sós. Ajtai, Komlós, and Szemerédi [AKS95] proved an asymptotic version, where at least $(1+\epsilon)n/2$ vertices have degree at least $(1+\epsilon)n/2$ (and $n$ is sufficiently large depending on $\epsilon$).

Komlós and Sós conjectured the generalisation that if at least $n/2$ vertices have degree at least $k$ then $G$ contains any tree with $k$ vertices.

See also the entry in the graphs problem collection.

Resolved by Alon [Al96], who showed that there exist constants $c_1,c_2>0$ such that \[\frac{m}{2}+c_1m^{4/5}\leq f(m)\leq \frac{m}{2}+c_2m^{4/5}.\]

See also the entry in the graphs problem collection.

Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman [Fo70], but with very poor quantitative bounds. (As a result these quantities are often called Folkman numbers.) Let this particular Folkman number be denoted by $N$.

Frankl and Rödl [FrRo86] proved $N\leq 7\times 10^{11}$, which Spencer [Sp88] improved to $\leq 3\times 10^{9}$. This resolved the challenge of Erdős [Er75d] to find such a graph with less than $10^{10}$ vertices.

Lu [Lu07] proved $N\leq 9697$ vertices. The current record is due to Dudek and Rödl [DuRo08] who proved $N\leq 941$ vertices. For further information we refer to a paper of Radziszowski and Xu [RaXu07], who prove that $N\geq 19$ and speculate that $N\leq 127$.

See also the entry in the graphs problem collection and [924] for the general case.

A problem of Erdős and Gallai. Lovász [Lo68] proved that every graph on $n$ vertices can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint paths and cycles, which implies that every graph can be partitioned into at most $n-1$ paths.

Chung [Ch78] proved that every connected graph on $n$ vertices can be partitioned into at most $\lceil n/2\rceil$ edge-disjoint trees. Pyber [Py96] has shown that every connected graph on $n$ vertices can be covered by at most $n/2+O(n^{3/4})$ paths.

If we drop the edge-disjoint condition then this conjecture was proved by Fan [Fa02].

Hajos [Lo68] has conjectured that if $G$ has all degrees even then $G$ can be partitioned into at most $\lfloor n/2\rfloor$ edge-disjoint cycles.

See also [184] and the entry in the graphs problem collection.

A problem of Erdős, Duke, and Rödl. Duke and Erdős [DuEr83], who proved the first if $n$ is sufficiently large depending on $\delta$. The real challenge is to prove this when $\delta=n^{-c}$ for some $c>0$. Duke, Erdős, and Rödl [DER84] proved the first statement with a $\delta^5$ in place of a $\delta^3$.

Fox and Sudakov [FoSu08b] have proved the second statement when $\delta >n^{-1/5}$.

See also the entry in the graphs problem collection.

Pyber, Rödl, and Szemerédi [PRS95] constructed such a graph with $\gg n\log\log n$ edges.

Chakraborti, Janzer, Methuku, and Montgomery [CJMM24] have shown that such a graph can have at most $n(\log n)^{O(1)}$ many edges. Indeed, they prove that there exists a constant $C>0$ such that for any $k\geq 2$ there is a $c_k$ such that if a graph has $n$ vertices and at least $c_kn(\log n)^{C}$ many edges then it contains $k$ pairwise edge-disjoint cycles with the same vertex set.

Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]. Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq \aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle.

A problem of Erdős and Hajnal (who proved this for chromatic number $\geq \aleph_2$). This was proved by Erdős, Hajnal, and Shelah [EHS74].

See also [593] and [737].

A problem of Erdős and Hajnal. Folkman [Fo70] and Nešetřil and Rödl [NeRo75] have proved that for every $n\geq 1$ there is a graph $G$ which contains no $K_4$ and is not the union of $n$ triangle-free graphs.

See also [582] and [596].

Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees).

Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595].

Erdős and Hajnal proved that $\omega_1^2 \to (\omega_1\omega,3)^2$. Erdős originally asked this with just the assumption that $G$ is $K_4$-free, but Baumgartner proved that $\omega_1^2 \not\to (\omega_1\omega, K_{\aleph_0,\aleph_0})^2$.

Sometimes known as the Erdős-Menger conjecture. When $G$ is finite this is equivalent to Menger's theorem. Erdős was interested in the case when $G$ is infinite.

This was proved by Aharoni and Berger [AhBe09].

Ruzsa and Szemerédi [RuSz78] proved that $e(n,r)=o(n^2)$ for any fixed $r$.

See also [80].

A problem of Erdős, Hajnal, and Milner [EHM70], who proved this is true for $\alpha < \omega_1^{\omega+2}$.

In [Er82e] Erdős offers \$250 for showing what happens when $\alpha=\omega_1^{\omega+2}$ and \$500 for settling the general case.

Larson [La90] proved this is true for all $\alpha<2^{\aleph_0}$ assuming Martin's axiom.

Erdős [Er97d] stated that, under the same assumptions, there at least $2n^2/9$ edges of $G$ which are contained in some odd cycle. He wrote that a positive answer to this question would follow if we knew that $G$ must contain a triangle such that there at least $n/2-O(1)$ vertices joined to at least two vertices of the triangle.

Erdős and Faudree observed that every graph with $2n$ vertices and at least $n^2+1$ edges has a triangle whose vertices are joined to at least $n+2$ vertices.

See also the entry in the graphs problem collection.

A problem of Erdős and Graham. The edges of $K_{2^n}$ can be $n$-coloured to avoid odd cycles of any length. It can be shown that $C_5$ and $C_7$ can be avoided for large $n$.

Chung [Ch97] asked whether $f(n)\to \infty$ as $n\to \infty$. Day and Johnson [DaJo17] proved this is true, and that \[f(n)\geq 2^{c\sqrt{\log n}}\] for some constant $c>0$. The trivial upper bound is $2^n$.

Girão and Hunter [GiHu24] have proved that \[f(n) \ll \frac{2^n}{n^{1-o(1)}}.\]

See also the entry in the graphs problem collection.

A problem of Erdős, Gallai, and Tuza, who proved that \[\tau(G) \leq n-\sqrt{2n}+O(1).\]

This would be best possible, since there exist triangle-free graphs with all independent sets of size $O(\sqrt{n\log n})$, which follows from the lower bound for $R(3,k)$ by Kim [Ki95] (see [165]).

Indeed, Erdős, Gallai, and Tuza speculate that if $f(n)$ is the largest $k$ such that every triangle-free graph on $n$ vertices contains an independent set on $f(n)$ vertices, then $\tau(G)\leq n-f(n)$.

In [Er94] and [Er99] Erdős asks for a weaker upper bound $\tau(G) \leq n-\omega(n)\sqrt{n}$ for any $\omega(n)\to \infty$.

See also [611], this entry and and this entry in the graphs problem collection.

A problem of Erdős, Gallai, and Tuza [EGT92], who proved for the latter question that $k_c(n) \geq n^{c'/\log\log n}$ for some $c'>0$, and that if every clique has size least $k$ then $\tau(G) \leq n-(kn)^{1/2}$. Bollobás and Erdős proved that if every maximal clique has at least $n+3-2\sqrt{n}$ vertices then $\tau(G)=1$ (and this threshold is best possible).

See also [610] and the entry in the graphs problem collection.

A problem of Erdős, Pach, Pollack, and Tuza [EPPT89], who gave constructions showing that the above bounds would be sharp, and proved the case $2r+1=3$. It is known (see [EPPT89] for example) that any connected graph on $n$ vertices with minimum degree $d$ has diameter \[D\leq 3\frac{n}{d+1}+O(1).\]

This was disproven for the case of $K_{2r}$-free graphs with $r\geq 2$ by Czabarka, Singgih, and Székely [CSS21], who constructed arbitrarily large connected graphs on $n$ vertices which contain no $K_{2r}$ and have minimum degree $d$, and diameter \[\frac{6r-5}{(2r-1)d+2r-3}n+O(1),\] which contradicts the above conjecture for each fixed $r$ as $d\to \infty$.

They suggest the amended conjecture, which no longer divides into two cases, that if $G$ is a connected graph on $n$ vertices with minimum degree $d$ which contains no $K_{k+1}$ then the diameter of $G$ is at most \[(3-\tfrac{2}{k})\frac{n}{d}+O(1).\] This bound is known under the weaker assumption that $G$ is $k$-colourable when $k=3$ and $k=4$, shown by Czabarka, Dankelmann, and Székely [CDS09] and Czabarka, Smith, and Székely [CSS23].

Cambie and Jooken [CaJo25] have given an example that shows the diameter for $K_4$-free graphs with minimum degree $16$ is at least $\frac{31}{216}n+O(1)$, giving another counterexample to the original conjecture.

See also the entry in the graphs problem collection.

Faudree proved that this is true if $G$ has $2n+1$ vertices.

See also the entry in the graphs problem collection.

See also the entry in the graphs problem collection.

A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi [EHSSS93]. In other words, if $\mathrm{rt}(n;k,\ell)$ is the Ramsey-Turán number then is it true that \[\mathrm{rt}(n; 4,n/\log n)< (1/8-c)n^2?\] Erdős, Hajnal, Sós, and Szemerédi [EHSS83] proved that for any fixed $\epsilon>0$ \[\mathrm{rt}(n; 4,\epsilon n)< (1/8+o(1))n^2.\] Sudakov [Su03] proved that \[\mathrm{rt}(n; 4,ne^{-f(n)})=o(n^2)\] whenever $f(n)/\sqrt{\log n}\to \infty$.

Resolved by Fox, Loh, and Zhao [FLZ15] who showed that the answer is no; in fact they prove that \[\mathrm{rt}(n; 4, ne^{-f(n)})\geq (1/8-o(1))n^2\] whenever $f(n) =o(\sqrt{\log n/\log\log n})$.

See also [22] and the entry in the graphs problem collection.

Erdős, Hajnal, and Tuza [EHT91] proved that this $t$ satisfies \[\frac{3}{16}r+\frac{7}{8}\leq t \leq \frac{1}{5}r.\]

In other words, there is no balanced colouring. A conjecture of Erdős and Gyárfás [ErGy99], who proved it for $r=3$ and $r=4$ (and observered it is false for $r=2$), and showed this property fails for infinitely many $r$ if we replace $r^2+1$ by $r^2$.

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98]. Simonovits showed that there exist graphs $G$ with maximum degree $\gg n^{1/2}$ and $h_2(G)\gg n^2$.

Erdős, Gyárfás, and Ruszinkó [EGR98] proved that if $G$ has no isolated vertices and maximum degree $O(1)$ then $h_2(G)\ll n\log n$.

Alon has observed this problem is essentially identical to [134], and his solution in this note also solves this problem in the affirmative.

See also [619].

A problem of Erdős, Gyárfás, and Ruszinkó [EGR98] who proved that $h_3(G)\leq n$ and $h_5(G) \leq \frac{n-1}{2}$ and there exist connected graphs $G$ on $n$ vertices with $h_3(G)\geq n-c$ for some constant $c>0$.

If we omit the condition that the graph must remain triangle-free then Alon, Gyárfás, and Ruszinkó [AGR00] have proved that adding $n/2$ edges always suffices to obtain diameter at most $4$.

See also [134] and [618].

This was first asked by Erdős and Rogers [ErRo62], and is generally known as the Erdős-Rogers problem. Let $f(n)$ be such that every such graph contains a triangle-free subgraph with at least $f(n)$ vertices.

It is now known that $f(n)=n^{1/2+o(1)}$. Bollobás and Hind [BoHi91] proved \[n^{1/2} \ll f(n) \ll n^{7/10+o(1)}.\] Krivelevich [Kr94] improved this to \[n^{1/2}(\log\log n)^{1/2} \ll f(n) \ll n^{2/3}(\log n)^{1/3}.\] Wolfovitz [Wo13] proved \[f(n) \ll n^{1/2}(\log n)^{120}.\]

A problem of Erdős, Gallai, and Tuza [EGT96], who observe that this is probably quite difficult since there are different examples where equality hold: the complete graph, the complete bipartite graph, and the graph obtained from $K_{m,m}$ by adding one vertex joined to every other.

A problem of Erdős and Faudree. Erdős writes 'it is easy to see' that there are at least $(\frac{1}{2}+o(1))2^{2n}$ sets that are not on a cycle.

If the regularity condition is replaced by minimum degree $n+1$ then the answer is no (consider $K_{n,n}$ with a spanning star in each part). Similarly this is false with degree $n$, as $K_{n,n}$ shows.

This has been resolved by Draganić, Keevash, and Müyesser [DKM25], who prove the asymptotically tight result that there are at least \[(\tfrac{1}{2}+o(1))2^{2n}\] subsets which are spanned by a cycle.

A problem of Erdős and Gimbel (see also [Gi16]). At a conference on random graphs in Poznan, Poland (most likely in 1989) Erdős offered \$100 for a proof that this is true, and \$1000 for a proof that this is false (although later told Gimbel that \$1000 was perhaps too much).

It is known that almost surely \[\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.\] (The final upper bound is due to Bollobás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)

Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability, \[\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.\] Heckel [He24c] further proved that, for any $\epsilon>0$, we have \[\chi(G) -\zeta(G) \geq n^{1-\epsilon}\] for roughly $95\%$ of all $n$.

It is known that \[\frac{1}{4\log k}\log n\leq g_k(n) \leq \frac{2}{\log(k-2)}\log n+1,\] the lower bound due to Kostochka [Ko88] and the upper bound to Erdős [Er59b].

Erdős [Er59b] proved that \[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\gg \frac{1}{m}\] and, for odd $m$, \[\lim_{n\to \infty}\frac{\log h^{(m)}(n)}{\log n}\leq \frac{2}{m+1},\] and conjectured this is sharp. He had no good guess for the value of the limit for even $m$, other that it should lie in $[\frac{2}{m+2},\frac{2}{m}]$, but could not prove this even for $m=4$.

See also the entry in the graphs problem collection.

Tutte and Zykov [Zy52] independently proved that for every $k$ there is a graph with $\omega(G)=2$ and $\chi(G)=k$. Erdős [Er61d] proved that for every $n$ there is a graph on $n$ vertices with $\omega(G)=2$ and $\chi(G)\gg n^{1/2}/\log n$, whence $f(n) \gg n^{1/2}/\log n$.

Erdős [Er67c] proved that \[f(n) \asymp \frac{n}{(\log n)^2}\] and that the limit in question, if it exists, must be in \[(\log 2)^2\cdot [1/4,1].\]

See also the entry in the graphs problem collection.

This property is sometimes called being $(a,b)$-splittable. A question of Erdős and Lovász (often called the Erdős-Lovász Tihany conjecture). Erdős [Er68b] originally asked about $a=b=3$ which was proved by Brown and Jung [BrJu69] (who in fact prove that $G$ must contain two vertex disjoint odd cycles).

Balogh, Kostochka, Prince, and Stiebitz [BKPS09] have proved the full conjecture for quasi-line graphs and graphs with independence number $2$.

See also the entry in the graphs problem collection.

A problem of Erdős, Rubin, and Taylor [ERT80], who proved that \[2^{k-1}<n(k) <k^22^{k+2}.\] They also prove that if $m(k)$ is the size of the smallest family of $k$-sets without property B (i.e. the smallest number of $k$-sets in a graph with chromatic number $3$) then $m(k)\leq n(k)\leq m(k+1)$.

Erdős, Rubin, and Taylor [ERT80] proved $n(2)=6$ and Hanson, MacGillivray, and Toft [HMT96] proved $n(3)=14$ and \[n(k) \leq kn(k-2)+2^k.\]

See also the entry in the graphs problem collection.

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer is yes, proved by Alon and Tarsi [AlTa92].

See also [631].

A problem of Erdős, Rubin, and Taylor [ERT80]. The answer to both is yes: Thomassen [Th94] proved that $\chi_L(G)\leq 5$ if $G$ is planar, and Voigt [Vo93] constructed a planar graph with $\chi_L(G)=5$. A simpler construction was given by Gutner [Gu96].

See also [630].

A problem of Erdős, Rubin, and Taylor [ERT80]. Note that $G$ is $(a,1)$-choosable corresponds to being $a$-choosable, that is, the list chromatic number satisfies $\chi_L(G)\leq a$.

This is false: Dvořák, Hu, and Sereni [DHS19] construct a graph which is $(4,1)$-choosable but not $(8,2)$-choosable.

See also the entry in the graphs problem collection.

A problem of Erdős, Faudree, and Sós, who proved there exist $\gg n^{3/2}$ many such subgraphs, and note that $n^{5/2}$ would be best possible.

This was proved by Kwan and Sudakov [KwSu21].

A problem of Erdős, Faudree, and Sós.

This was proved by Bukh and Sudakov [BuSu07].

Jenssen, Keevash, Long, and Yepremyan [JKLY20] have proved that there must exist an induced subgraph which contains $\gg n^{2/3}$ distinct degrees (with no restriction on the number of vertices).

Erdős writes 'if the answer is affirmative many extensions and generalisations will be possible'.

Solved by Erdős, Rousseau, and Schelp for large $n$, but unpublished. Alon has observed that this also follows from a result of Pyber [Py86], which states that (for large enough $n$) at most $\lfloor n^2/4\rfloor+2$ monochromatic cliques cover all edges of a $2$-coloured $K_n$.

This problem was solved completely by Keevash and Sudakov [KeSu04], who provd that the corret threshold is $\lfloor n^2/4\rfloor$ for all $n\geq 7$, is $\binom{n}{2}$ for $n\leq 5$, and is $10$ for $n=6$.

A problem of Erdős and Hajnal.

A problem of Erdős and Hajnal.

This was resolved in the negative by Janzer, Steiner, and Sudakov [JSS24] - in fact, this fails even at $k=2$. Janzer, Steiner, and Sudakov proved that there exists a constant $c>0$ such that, for all large $n$, there exists a graph on $n$ vertices with chromatic number \[\geq c\frac{\log\log n}{\log\log \log n}\] which contains no $4$-regular subgraph.

A problem of Hamburger and Szegedy.

For $n=2$ this is asking for the maximal number of edges on a graph which contains no $C_4$, and so $f(n;2)=(1+o(1))n^{3/2}$.

Füredi proved that $f(n;3) \ll n^2$ and $f(n;3) > \binom{n}{2}$ for infinitely many $n$. More generally, Füredi proved that \[f(n;t) \ll \binom{n}{t-1}.\]

In [Er91] Erdős further suggests that perhaps, for every $k\geq 3$, there are constants $c$ and $a_k<1$ such that every subgraph with at least $cn^{a_k}2^n$ many edges contains a $C_{2k}$, where $a_k\to 0$ as $k\to \infty$.

The answer to this problem is no: Chung [Ch92] and Brouwer, Dejter, and Thomassen [BDT93] constructed an edge-partition of $Q_n$ into four subgraphs, each containing no $C_6$.

See also [86].

A problem of Erdős, Faudree, Rousseau, and Schelp.

When $q=1$ this corresponds exactly to the classical Ramsey problem, and hence for example \[\frac{1}{p-1}\leq c(p,1) \leq \frac{2}{p+1}.\] It is easy to see that if $q=\binom{p-1}{2}+1$ then $c(p,q)=1$. Erdős, Faudree, Rousseau, and Schelp have shown that $c(p,\binom{p-1}{2})\leq 1/2$.

A generalisation of the Hadwiger-Nelson problem (which addresses $n=2$). Frankl and Wilson [FrWi81] proved exponential growth: \[\chi(G_n) \geq (1+o(1))1.2^n.\] The trivial colouring (by tiling with cubes) gives \[\chi(G_n) \leq (2+\sqrt{n})^n.\] Larman and Rogers [LaRo72] improved this to \[\chi(G_n) \leq (3+o(1))^n,\] and conjecture the truth may be $(2^{3/2}+o(1))^n$. Prosanov [Pr20] has given an alternative proof of this upper bound.

See also [508], [705], and [706].

The maximal value of $\chi(G)$ (without a girth condition) is the Hadwiger-Nelson problem. There are unit distance graphs (e.g. the Moser spindle) with $\chi(G)=4$ of girth $3$. de Grey [dG18] has constructed a unit distance graph $G$ with $\chi(G)=5$. (I do not know what the largest girth achieved is by these recent constructions.)

Wormald [Wo79] has constructed a unit distance graph with $\chi(G)=4$ and girth $5$, with $6448$ vertices. O'Donnell [OD94] has constructed a unit distance graph with $\chi(G)=4$ and girth $4$, with $56$ vertices. Chilakamarri [Ch95] has constructed an infinite family of unit distance graphs with $\chi(G)=4$ and girth $4$, the smallest of which has $47$ vertices.

See also [508], [704], and [706].

The case $r=1$ is the Hadwiger-Nelson problem, for which it is known that $5\leq L(1)\leq 7$.

See also [508], [704], and [705].

Turán proved that, when $r=2$, this limit is \[\frac{1}{2}\left(1-\frac{1}{k-1}\right).\] Erdős [Er81] offered \$500 for the determination of this value for any fixed $k>r>2$, and \$1000 for 'clearing up the whole set of problems'.

See also [500] for the case $r=3$ and $k=4$.

A problem of Erdős and Simonovits. This is not true for hypergraphs, as shown by Ruzsa and Szemerédi [RuSz78], who proved that if $G$ is a $3$-uniform hypergraph on $6$ vertices containing $3$ $3$-edges then $\mathrm{ex}_3(n;G)=o(n^2)$ and yet for every $\epsilon >0$ \[\mathrm{ex}_3(n;G) >n^{2-\epsilon}\] for all large enough $n$.

See also [571].

Kövári, Sós, and Turán [KST54] proved \[\mathrm{ex}(n; K_{r,r}) \ll n^{2-1/r}.\] Brown [Br66] proved the conjectured lower bound when $r=3$.

See also [147].

A problem of Berge (or Berge and Sauer). Alon, Friedland, and Kalai [AFK84] proved that every $4$-regular graph plus an edge contains a $3$-regular subgraph, and hence in particular every $r$-regular graph with $r\geq 5$ contains a $3$-regular subgraph.

The answer is yes, proved by Tashkinov [Ta82].

A conjecture of Brown, Erdős, and Sós. The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known as the Ruzsa-Szemerédi problem).

In [Er81] Erdős asks whether the same is true for any $3$-uniform hypergraph on $k$ vertices with $k-3$ $3$-edges.

Hajós originally conjectured that $\chi(G)\leq \sigma(G)$, which was proved by Dirac [Di52] when $\chi(G)=4$. Catlin [Ca74] disproved Hajós' conjecture for all $\chi(G)\geq 7$, and Erdős and Fajtlowicz [ErFa81] disproved it in a strong form, showing that in fact for almost all graphs on $n$ vertices, \[\chi(G) \gg \frac{n^{1/2}}{\log n}\sigma(G).\]

The answer is yes, proved by Fox, Lee, and Sudakov [FLS13].

A conjecture of Erdős, Hajnal, and Mader. Dirac [Di60] proved that every graph on $n$ vertices with at least $2n-2$ edges contains a subdivision of $K_4$, and conjectured that $3n-5$ edges forces a subdivision of $K_5$.

Mader [Ma67] proved that $\geq 2^{\binom{r}{2}}n$ edges suffices.

The answer is yes, proved independently by Komlós and Szemerédi [KoSz96] and Bollobás and Thomason [BoTh96].

A conjecture of Erdős and Sauer.

A problem of Erdős, Faudree, Rousseau, and Schelp [EFRS78b].

Answered by Beck [Be83b], who proved that in fact $\hat{R}(P_n)\ll n$ and $\hat{R}(C_n)\ll n$.

A conjecture of Walter Taylor.

More generally, Erdős asks to characterise families $\mathcal{F}_\alpha$ of finite graphs such that there is a graph of chromatic number $\aleph_\alpha$ all of whose finite subgraphs are in $\mathcal{F}_\alpha$.

A problem of Erdős, Hajnal, and Shelah [EHS74], who proved that $G$ must contain all sufficiently large cycles (see [594]).

A conjecture of Gyárfás.

A question of Galvin, who proved that the answer is no if we ask for the subgraph to be induced (assuming $\aleph_1 < 2^{\aleph_0}$).

A question of Erdős and Hajnal. Rödl proved this is true if $\mathfrak{m}=\aleph_0$ and $r=3$ (see [108] for the finitary version).

More generally, Erdős and Hajnal asked must there exist (for every cardinal $\mathfrak{m}$ and integer $r$) some $f_r(\mathfrak{m})$ such that every graph with chromatic number $\geq f_r(\mathfrak{m})$ contains a subgraph with chromatic number $\mathfrak{m}$ with no odd cycle of length $\leq r$?

Erdős [Er95d] claimed that even the $r=3$ case of this is open: must every graph with sufficiently large chromatic number contain a triangle free graph with chromatic number $\mathfrak{m}$?

In [Er81] Erdős also asks the same question but with girth (i.e. the subgraph does not contain any cycle at all of length $\leq C$).

A conjecture of Murty and Plesnik (see [CaHa79]) (although Füredi credits this conjecture to Murty and Simon, and further mentions that Erdős told him that the conjecture goes back to Ore in the 1960s). The complete bipartite graph shows that this would be best possible.

This is true (for sufficiently large $n$) and was proved by Füredi [Fu92].

A conjecture of Gyárfás, known as the tree packing conjecture.

Gyárfás and Lehel [GyLe78] proved that this holds if all but at most $2$ of the trees are stars, or if all the trees are stars or paths. Fishburn [Fi83] proved this for $n\leq 9$. Bollobás [Bo83] proved that the smallest $\lfloor n/\sqrt{2}\rfloor$ many trees can always be packed greedily into $K_n$.

Joos, Kim, Kühn, and Osthus [JKKO19] proved that this conjecture holds when the trees have bounded maximum degree. Allen, Böttcher, Clemens, Hladky, Piguet, and Taraz [ABCHPT21] proved that this conjecture holds when all the trees have maximum degree $\leq c\frac{n}{\log n}$ for some constant $c>0$.

Janzer and Montgomery [JaMo24] have proved that there exists some $c>0$ such that the largest $cn$ trees can be packed into $K_n$.

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Odd cycles show that $f_3(n)=1$, but they expected $f_4(n)\to \infty$. Gallai [Ga68] gave a construction which shows \[f_4(n) \ll n^{1/2},\] and Lovász extended this to show \[f_k(n) \ll n^{1-\frac{1}{k-2}}.\]

This conjecture was disproved by Rödl and Tuza [RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).

Erdős believed that almost surely the second largest component has size $\ll \log n$. This is true, as proved by Komlós, Sulyok, and Szemerédi [KSS80].

A conjecture of Erdős and Rényi [ErRe66], who proved that almost surely such a graph has a perfect matching (when $n$ is even).

This is true. Pósa [Po76] proved that almost surely a random graph with $\geq Cn\log n$ edges is Hamiltonian for some large constant $C$, and Komlós and Szemerédi [KoSz83] proved that \[\geq \frac{1}{2}n\log n+\frac{1}{2}n\log\log n+w(n)n\] edges suffices, for any function $w$ which $\to \infty$ as $n\to \infty$.

In [Er69b] Erdős conjectures this for $f(m)=\epsilon m$ for any fixed $\epsilon>0$. In [Er94b] he claims this weaker conjecture was proved by himself and Hajnal, but gives no reference.

In [ErHa67b] Erdős and Hajnal prove this for $f(m)\geq cm$ for all $c>1/4$.

See also [75].

The answer is no: Bondy and Vince [BoVi98] proved that every graph with minimum degree at least $3$ has two cycles whose lengths differ by at most $2$, and hence the same is true for every graph with chromatic number $4$.

A question of Erdős, Faudree, and Schelp, who proved it when $s=2$.

The answer is yes, proved by Sudakov and Verstraëte [SuVe08], who in fact proved that under the assumption of average degree $k$ and girth $>2s$ there are at least $\gg k^s$ many consecutive even integers which are cycle lengths in $G$.

A problem of Erdős, Rubin, and Taylor.

The answer is no: Alon [Al92] proved that, for every $n$, there exists a graph $G$ on $n$ vertices such that \[\chi_L(G)+\chi_L(G^c)\ll (n\log n)^{1/2},\] where the implied constant is absolute.

A question of Erdős and Gimbel, who knew that $4\leq z(12)\leq 5$ and $5\leq z(15)\leq 6$. The equality $z(12)=4$ would follow from proving that if $G$ is a graph on $12$ vertices such that both $G$ and its complement are $K_4$-free then either $\chi(G)\leq 4$ or $\chi(G^c)\leq 4$.

In fact there do exist such graphs - Bhavik Mehta found computationally that there is exactly one (up to taking the complement) graph on $12$ vertices such that both $G$ and its complement are $K_4$-free with chromatic number $\geq 5$. This graph was explicitly checked to have cochromatic number $4$, and hence this proves that indeed $z(12)=4$.

The values of $z(n)$ are now known for $1\leq n\leq 19$: \[1,1,2,2,3,3,3,3,4,4,4,4,5,5,5,6,6,6,6.\] (The only significant difficulty here is proving $z(12)=4$ - the others follow from easy inductive arguments and the facts that $R(3)=6$ and $R(4)=18$.) It is unknown whether $z(20)=6$ or $7$.

Gimbel [Gi86] has shown that $z(n) \asymp \frac{n}{\log n}$.

A problem of Erdős and Gimbel. Gimbel [Gi86] proved that \[\frac{\sqrt{n}}{\log n}\ll z(S_n) \ll \sqrt{n}.\] Solved by Gimbel and Thomassen [GiTh97], who proved \[z(S_n) \asymp \frac{\sqrt{n}}{\log n}.\]

A problem of Erdős and Gimbel, who proved that there must exist a subgraph $H$ with \[\zeta(H) \gg \left(\frac{m}{\log m}\right)^{1/2}.\] The proposed bound would be best possible, as shown by taking $G$ to be a complete graph.

The answer is yes, proved by Alon, Krivelevich, and Sudakov [AKS97].

The first question is due to Erdős and Neumann-Lara. The second question is due to Erdős and Gimbel. A positive answer to the second question implies a positive answer to the first via the bound mentioned in [760].

A conjecture of Erdős, Gimbel, and Straight [EGS90], who proved that for every $n>2$ there exists some $f(n)$ such that if $G$ contains no clique on $n$ vertices then $\chi(G)\leq \zeta(G)+f(n)$.

This has been disproved by Steiner [St24b], who constructed a graph $G$ with $\omega(G)=4$, $\zeta(G)=4$, and $\chi(G)=7$.

Erdős and Klein [Er38] proved $\mathrm{ex}(n;C_4)\asymp n^{3/2}$. Reiman [Re58] proved \[\frac{1}{2\sqrt{2}}\leq \lim \frac{\mathrm{ex}(n;C_4)}{n^{3/2}}\leq \frac{1}{2}.\] Erdős and Rényi, and independently Brown, gave a construction that proved if $n=q^2+q+1$, where $q$ is a prime power, then \[\mathrm{ex}(n;C_4)\geq\frac{1}{2}q(q+1)^2.\] Coupled with the upper bound of Reiman this implies that $\mathrm{ex}(n;C_4)\sim\frac{1}{2}n^{3/2}$ for all large $n$. Füredi [Fu83] proved that if $q>13$ then \[\mathrm{ex}(n;C_4)=\frac{1}{2}q(q+1)^2.\]

See also [572].

Dirac and Erdős proved independently that when $l=\lfloor k^2/4\rfloor+1$ \[f(n;k,l)\leq \lfloor n^2/4\rfloor+1.\]

Czipszer proved that $g_k(n)$ exists for all $k$, and in fact $g_k(n)\leq (k+1)n$. Erdős wrote it is 'easy to see' that \[g_k(n)\geq (k+1)n-(k+1)^2.\] Pósa proved that $g_1(n)=2n-4$ for $n\geq 4$. Erdős could prove the conjectured equality for $n\geq 2k+2$ when $k=2$ or $k=3$.

The conjectured equality was proved for $n\geq 3k+3$ by Jiang [Ji04].

Curiously, in [Er69b] Erdős mentions this problem, but states that his conjectured equality for $g_k(n)$ was disproved (for general $k$) by Lewin, citing oral communication. Perhaps Lewin only disproved this for small $n$, or perhaps Lewin's disproof was simply incorrect.

Erdős constructed such a hypergraph with cliques of at least $n-\log_*n$ different sizes. For graphs, Spencer [Sp71] constructed a graph which contains cliques of at least $n-\log_2n+O(1)$ different sizes, which Moon and Moser [MoMo65] showed to be best possible.

See also [927].

A problem of Daykin and Erdős. Daykin and Frankl proved that if there are $(1+o(1))\binom{m}{2}$ edges then $m^{1/n}\to 1$ as $n\to \infty$.

For the first question we need to take $\epsilon>0$ since since if $n$ is even and $m=2^{n/2+1}$ one could take $\mathcal{F}$ to be all subsets of $\{1,\ldots,n/2\}$ together with $\{1,\ldots,n/2\}$ union all subsets of $\{n/2+1,\ldots,n\}$, which produces $2^{n}$ edges.

The third question was answered in the affirmative by Alon and Frankl [AlFr85], who proved that, for every $k\geq 1$, if $m=2^{(\frac{1}{k+1}+\delta)n}$ for some $\delta>0$ then the number of edges is \[< \left(1-\frac{1}{k}\right)\binom{m}{2}+O(m^{2-\Omega_k(\delta^{k+1})}).\] They also answer the second question in the negative, noting that if $\mathcal{F}$ is the family of sets which either intersect $\{n/2+1,\ldots,n\}$ in at most $1$ element or intersect $\{1,\ldots,n/2\}$ in at least $n/2-1$ elements then $m \gg n2^{n/2}$ and there are at least $2^{-5}\binom{m}{2}$ edges.

Finally, an affirmative answer to the first question follows from Theorem 1.4 and Corollary 1.5 of Alon, Das, Glebov, and Sudakov [ADGS15].

Malekshahian and Spiro [MaSp24] have proved that, for the first game, the set of $n$ for which Bob wins has density at least $3/4$ - in fact they prove that if Alice wins at $n$ then Bob wins at $n+1,n+2,n+3$.

Similarly, for the third game they prove that the set of $n$ for which Bob wins has density at least $2/3$, and prove the stronger statement that if Alice wins at $n$ then Bob wins at $n+1,n+2$.

Balogh has observed that this problem is probably misstated by Erdős - indeed, every graph with $5$ vertices spanning $7$ edges contains a graph on $4$ vertices spanning $3$ edges, so the second condition can be dropped.

This problem is then now asking how many edges a $3$-uniform hypergraph can have before it contains $K_4$ minus an edge, and whether the critical edge density is $2/9$. In fact there is a construction of Frankl and Füredi [FrFu84] showing it must be at least $2/7$, which is the conjectured truth (although Turán conjectured before [Er69] that that the edge density was $1/4$, and so likely there is simply a typo in this problem's statement).

Harris has provided the following simple counterexample to the problem as stated: the $3$-uniform graph on $\{1,\ldots,9\}$ with $28$ edges, formed by taking $27$ edges by choosing one element each from $\{1,2,3\},\{4,5,6\},\{7,8,9\}$, and then adding the edge $\{1,2,3\}$.

It is easy to see that $f(d)\leq d^2+1$ using a greedy colouring. Erdős had shown $f(d)\geq d^{4/3-o(1)}$.

Resolved by Alon, McDiarmid, and Reed [AMR91] who showed \[\frac{d^{4/3}}{(\log d)^{1/3}}\ll f(d) \ll d^{4/3}.\]

A problem of Erdős, Rubin and Taylor.

The answer is yes: Alon [Al92] proved that in fact the random graph on $n$ vertices with edge probability $1/2$ has \[\chi_L(G) \ll \frac{\log\log n}{\log n}n\] almost surely. Alon, Krivelevich, and Sudakov [AKS99] improved this to \[\chi_L(G) \asymp \frac{n}{\log n}\] almost surely.

A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94]. This is a special case of [163].

Proved by Alon [Al96b].

A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81], who proved that there must exist an independent set on \[\gg_r \frac{\log\log(t+1)}{t}n\] many vertices. Shearer [Sh95] improved this to \[\gg_r \frac{\log t}{\log\log(t+1)t}n.\] Ajtai, Komlós, and Szemerédi [AKS80] proved the conjectured bound when $r=3$. Alon [Al96b] proved the conjectured bound, but replacing the $K_r$-free assumption with the stronger assumption that the induced graph on every vertex neighbourhood has chromatic number $\leq r-2$.

A problem of Erdős and Simonovits [ErSi70], who proved a similar claim replacing $\log n$ and $\log m$ by $n^{c}$ and $m^c$ respectively, for any constant $c>0$ (where the balance parameter may depend on $c$).

Alon [Al08] proved this is actually false: for every $D>1$ and $n>10^5$ there is a graph $G$ with $\leq 2n$ vertices and $\geq 2n\log(2n)$ edges such that if $H$ is a $D$-balanced subgraph then $H$ has $\ll m(\sqrt{\log m}+\log D)$ many edges.

A question of Erdős and Hajnal. Alon and Sudakov [AlSu07] proved that in fact \[\frac{(\log n)^2}{\log\log n}\ll f((\log n)^2,n) \ll (\log n)^2\] and \[f((\log n)^3,n)\asymp \frac{(\log n)^2}{\log\log n}.\]

See also [805].

A problem of Erdős and Hajnal, who thought that there is no such graph for $g(n)=(\log n)^3$. Alon and Sudakov [AlSu07] proved that there is no such graph with \[g(n)=\frac{c}{\log\log n}(\log n)^3\] for some constant $c>0$.

Alon, Bucić, and Sudakov [ABS21] construct such a graph with \[g(n)\leq 2^{2^{(\log\log n)^{1/2+o(1)}}}.\] See also [804].

Alon [Al15] showed this is false: in fact almost surely $\tau(G) \leq n-\alpha(G)-1$. Alon, Bohman, and Huang [ABH17] proved that in fact there is some absolute constant $c>0$ such that almost surely \[\tau(G) \leq n-(1+c)\alpha(G).\]

A problem of Erdős and Szemerédi, which strengthens the conjecture [52].

This strong conjecture was disproved by Alon, Ruzsa, and Solymosi [ARS20], who constructed (for arbitrarily large $n$) a set of integers $A$ with $\lvert A\rvert=n$ and a graph $G$ with $\gg n^{5/3-o(1)}$ many edges such that \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \ll \lvert A\rvert^{4/3+o(1)}.\] Alon, Ruzsa, and Solymosi do prove, however, that if $A$ has size $n$ and $G$ has $m$ edges then \[\max(\lvert A+_GA\rvert,\lvert A\cdot_G A\rvert) \gg m^{3/2}n^{-7/4}.\]

A problem of Burr, Erdős, Graham, and Sós, who proved that \[F_k(n)\gg n^2.\]

See also [810].

A problem of Burr, Erdős, Graham, and Sós.

See also [809].

A problem of Erdős, Pyber, and Tuza, who observe that if $d_G(n)$ exists then $d_G(n) < \frac{n-1}{e(G)}$.

The Kürschák competition in Hungary in 1986 asked students to prove that $d_{K_3}(n)$ exists. Kostochka proved that $d_{K_3}(n)=n/4$ is the best possible. Tuza proved that \[d_{C_4}(n) \leq \left(\frac{1}{4}-c\right)n\] for some constant $c>0$. Brightwell and Trotter proved that \[d_{C_6}(n) > (1-o(1))\frac{n}{6}.\]

Burr, Erdős, Faudree, and Schelp [BEFS89] proved that \[R(n+1)-R(n) \geq 4n-8\] for all $n\geq 2$. The lower bound of [165] implies that \[R(n+2)-R(n) \gg n^{2-o(1)}.\]

A problem of Erdős and Hajnal, who could prove that \[n^{1/3}\ll h(n) \ll n^{1/2}.\]

Bucić and Sudakov [BuSu23] have proved \[h(n) \gg n^{5/12-o(1)}.\]

The case $k=3$ was a problem of Erdős and Hajnal [Er91]. The question for general $k$ was a conjecture of Erdős, Faudree, Rousseau, and Schelp [EFRS90], who proved that such a subgraph exists with at most $n-c_k\sqrt{n}$ vertices. Mousset, Noever, and Skorić [MNS17] improved this to \[n-c_k\frac{n}{\log n}.\] The full conjecture was proved by Sauermann [Sa19], who proved this with $c_k \gg 1/k^3$.

In [Er91] Erdős attributes this to himself and Hajnal, claiming they could prove it for $3\leq k\leq 6$, but it appears in an earlier paper of Erdős, Faudree, Gyárfás, and Schelp [EFGS88], where they prove that such a graph on $n\geq 5$ vertices contains cycles of length $3$, $4$, and $5$, and a cycle of length at least $\lfloor \log_2n\rfloor$, and need not contain a cycle of length longer than $\sqrt{n}$.

Such graphs are called degree $3$ critical. This conjecture was disproved by Narins, Pokrovskiy, and Szabó [NPS17], who proved that there are arbitrarily large such graphs with no cycle of length $23$.

It remains open whether this question has an affirmative answer if we restrict to even $k$.

A problem of Erdős and Hajnal. The example of $K_{n,n+1}$ shows that this fails if we only have $n^2+n$ edges.

This is true, and was proved by Chen and Ma [ChMa25], who prove the stronger statement that, provided $n\geq 600$, all graphs with $2n+1$ vertices and at least $n^2+n$ edges contain two vertices of the same degree joined by a path of length $3$, except $K_{n,n+1}$.

When $r=2$ it is a classical fact that chromatic number $k$ implies at least $\binom{k}{2}$ edges. Erdős asked for $k$ to be large in this conjecture since he knew it to be false for $r=k=3$, as witnessed by the Steiner triples with $7$ vertices and $7$ edges.

This was disproved by Alon [Al85], who proved, for example, that there exists some absolute constant $C>0$ such that if $r\geq C$ and $k\geq Cr$ then there exists an $r$-uniform hypergraph with chromatic number $\geq k$ with at most \[\leq (7/8)^r\binom{(r-1)(k-1)+1}{r}\] many edges.

In general, Alon gave an upper bound for the minimal number of edges using Turán numbers. Using known bounds for Turán numbers then suffices to disprove this conjecture for all $r\geq 4$. The validity of this conjecture for $r=3$ remains open.

If $m(r,k)$ denotes the minimal number of edges of any $r$-uniform hypergraph with chromatic number $>k$ then Akolzin and Shabanov [AkSh16] have proved \[\frac{r}{\log r}k^r \ll m(r,k) \ll (r^3\log r) k^r,\] where the implied constants are absolute. Cherkashin and Petrov [ChPe20] have proved that, for fixed $r$, $m(r,k)/k^r$ converges to some limit as $k\to \infty$.

In general, determine the largest integer $f(r)$ such that every $r$-uniform hypergraph with chromatic number $3$ has a vertex contained in at least $f(r)$ many edges. It is easy to see that $f(2)=2$ and $f(3)=3$. Erdős did not know the value of $f(4)$.

This was solved by Erdős and Lovász [ErLo75], who proved in particular that there is a vertex contained in at least \[\frac{2^{r-1}}{4r}\] many edges.

A problem of Erdős and Lovász.

They do not specify what is meant by $3$-critical. One definition in the literature is: a hypergraph is $3$-critical if there is a set of $3$ vertices which intersects every edge, but no such set of size $2$, and yet for any edge $e$ there is a pair of vertices which intersects every edge except $e$. Raphael Steiner observes that a $3$-critical hypergraph in this sense has bounded size, so this problem would be a finite computation, and perhaps is not what they meant.

An alternative definition is that a hypergraph is $3$-critical if it has chromatic number $3$, but its chromatic number becomes $2$ after deleting any edge or vertex.

A problem of Erdős and Rosenfeld. This is trivially possible for $k=2$. They were not sure about $k=6$.

This is equivalent to asking whether there exists $k>2$ such that the chromatic number of the Johnson graph $J(2k,k)$ is $k+1$ (it is always at least $k+1$ and at most $2k$). The chromatic numbers listed at this website show that this is false for $3\leq k\leq 8$.

A problem of Erdős and Shelah. The Fano geometry gives an example where there are no two edges which meet in $r-1$ vertices. Are there any other examples?

Erdős and Lovász [ErLo75] proved that there must be two edges which meet in $\gg \frac{r}{\log r}$ many vertices.

Alon has provided the following counterexample to the first question: as vertices take two sets $X$ and $Y$ of sizes $2r-2$ and $\frac{1}{2}\binom{2r-2}{r-1}$ respectively, where $Y$ corresponds to all partitions of $X$ into two equal parts. The edges are all subsets of $X$ of size $r$, and also all sets consisting of a subset of $X$ of size $r-1$ together with the unique element of $Y$ corresponding to the induced partition of $X$.

This hypergraph is intersecting, its chromatic number is $3$, and it has $\asymp 4^r/\sqrt{r}$ many vertices.

A problem of Erdős and Simonovits. It is known that \[A_2 = \left\{ 1-\frac{1}{k} : k\geq 1\right\}.\]

The answer is yes, proved by Fleischner and Stiebitz [FlSt92].

A problem of Erdős and Sárkőzy [ErSa97], who prove that if \[\lvert A\rvert >\lfloor\tfrac{n}{2}\rfloor+\lfloor\tfrac{n}{3}\rfloor-\lfloor\tfrac{n}{6}\rfloor\] then $G(A)$ contains all odd cycles of length $\leq cn$ for some constant $c>0$.

This threshold is the best possible, since one could take $A$ to be the set of $m\leq n$ which are divisible by either $2$ or $3$, in which case $G(A)$ contains no triangles.

A problem of Erdős and Hajnal. Hajnal thought that there is in fact an independent set which is a Hindman set - that is, an independent set of the shape \[\left\{ \sum_{i\in S}a_i : S\subseteq \{1,\ldots,k\}\right\}\] for some $a_1,\ldots,a_k$ (provided $n$ is sufficiently large depending on $k$).

The stated problem has been resolved by Barber (personal communication) who verified using a SAT solver that this is true for all $n\geq 18$. The general question of an independent Hindman set remains open.

This was proved by Ajtai, Komlós, and Szemerédi [AKS81].

Schütte asked Erdős this in the early 1960s.

It is easy to check that $f(1)=3$ and $f(2)=7$. Erdős [Er63c] proved \[2^{n+1}-1 \leq f(n) \ll n^22^n.\] Szekeres and Szekeres [SzSz65] proved that $f(3)=19$ and \[n2^n \ll f(n).\]

A conjecture of Bollobás and Erdős. This was proved by Edwards [Ed78].

A conjecture of Bollobás and Erdős. This was proved independently by Edwards (unpublished) and Hadziivanov and Nikiforov [KhNi79].

For a more general problem see [80].

When $r=2$ this follows from Dirac's theorem. Corrádi and Hajnal [CoHa63] proved this when $r=3$. Hajnal and Szemerédi [HaSz70] proved this for all $r\geq 4$.

A conjecture of Bollobás and Erdős [BoEr62]. This would be best possible, as demonstrated by $n$ disjoint copies of $K_m$ and a disjoint vertex.

Bollobás proved this when $m=4$ - in fact he showed that every graph with $n$ vertices and $2n-1$ edges contains two points joined by $4$ edge-disjoint paths.

This would be a stronger form of the result of Dirac [Di60] that every such graph contains a subgraph homeomorphic to $K_4$.

The answer is yes, as proved by Thomassen [Th74].

Dirac [Di52] proved \[f_6(4n+2) \geq 4n^2+8n+3,\] as witnessed by taking two disjoint copies of $C_{2n+1}$ and adding all edges between them.

Erdős [Er69b] observed that Dirac's construction generalises to show that, if $3\mid k$, there are infinitely many values of $n$ (those of the shape $mk/3$ where $m$ is odd) such that \[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{k/3}\right)n^2 + n.\]

Toft [To70] proved that $f_k(n)\gg_k n^2$ for $k\geq 4$.

Constructions of Stiebitz [St87] show that, for $k\geq 6$, there exist infinitely many values of $n$ such that \[f_k(n) \geq \frac{1}{2}\left(1-\frac{1}{\lfloor k/3\rfloor+\delta_k}\right)n^2\] where $\delta_k=0$ if $k\equiv 0\pmod{3}$, $\delta_k=1/7$ if $k\equiv 1\pmod{3}$, and $\delta_k\equiv 24/69$ if $k\equiv 2\pmod{3}$, which disproves Erdős' conjectured asympotic for $k\not\equiv 0\pmod{3}$.

Stiebitz also proved the general upper bound \[f_k(n) < \mathrm{ex}(n;K_{k-1})\sim \frac{1}{2}\left(1-\frac{1}{k-2}\right)n^2\] for large $n$. Luo, Ma, and Yang [LMY23] have improved this upper bound to \[f_k(n) \leq \frac{1}{2}\left(1-\frac{1}{k-2}-\frac{1}{36(k-1)^2}+o(1)\right)n^2\]

A question of Erdős and Hajnal [ErHa68b], who proved that for every finite $k$ there is a graph with chromatic number $\aleph_1$ where each subgraph on less than $\aleph_k$ vertices has chromatic number $\leq \aleph_0$.

This question was inspired by a theorem of Babai, that if $G$ is a graph on a well-ordered set with chromatic number $\geq \aleph_0$ there is a subgraph on vertices with order-type $\omega$ with chromatic number $\aleph_0$.

Erdős and Hajnal showed this does not generalise to higher cardinals - they (see [Er69b]) constructed a set on $\omega_1^2$ with chromatic number $\aleph_1$ such that every strictly smaller subgraph has chromatic number $\leq \aleph_0$ as follows: the vertices of $G$ are the pairs $(x_\alpha,y_\beta)$ for $1\leq \alpha,\beta <\omega_1$, ordered lexicographically. We connect $(x_{\alpha_1},y_{\beta_1})$ and $(x_{\alpha_2},y_{\beta_2})$ if and only if $\alpha_1<\alpha_2$ and $\beta_1<\beta_2$.

A similar construction produces a graph on $\omega_2^2$ with chromatic number $\aleph_2$ such that every smaller subgraph has chromatic number $\leq \aleph_1$.

Graver and Yackel [GrYa68] proved that \[g_k(n) \ll \left(n\frac{\log\log n}{\log n}\right)^{1-\frac{1}{k-1}}.\] Erdős [Er59b] proved that \[g_3(n) \gg \frac{n^{1/2}}{\log n},\] by proving $R(3,m)\gg (m/\log m)^2$. Shearer's lower bound for $R(3,m)$ (see [165]) improves this to \[g_3(n) \gg \left(\frac{n}{\log n}\right)^{1/2}.\]

The lower bound $R(4,m) \gg m^3/(\log m)^4$ of Mattheus and Verstraete [MaVe23] (see [166]) implies \[g_4(n) \gg \frac{n^{2/3}}{(\log n)^{4/3}}.\] In general it is known (see [BoKe10]) that \[R(k,m)\gg (\log m)^{-O_k(1)}m^{\frac{k+1}{2}}\] which implies \[g_k(n) \gg \frac{n^{1-\frac{2}{k+1}}}{(\log n)^{c_k}}.\]

A question of Erdős and Gallai. Gallai [Ga63] proved that \[f_4(n) \gg n^{1/2}\] and Erdős (unpublished) proved $f_4(n) \ll n^{1/2}$.

This was proved for all $k\geq 4$ by Kierstead, Szemerédi, and Trotter [KST84].

A question of Erdős and Hajnal [ErHa67b]. The case $k=0$ is trivial, but they could not prove this even for $k=1$.

This is true, and was proved by Folkman [Fo70b].

See also [73].

This is true, as shown by Rödl [Ro77].

See [108] for a more general question.

A question of Erdős and Hajnal. Folkman [Fo70] proved this when $k=2$. The case for general $k$ was proved by Nešetřil and Rödl [NeRo76].

See [582] for a special case.

It is easy to show that there exists an independent set of size $\gg n^{1/3}$.

In other words, this question asks whether $R(3,3,m) \ll m^{3-c}$ for some $c>0$. This was disproved by Alon and Rödl [AlRo05], who proved that \[\frac{1}{(\log m)^{4+o(1)}}m^3 \ll R(3,3,m) \ll \frac{\log\log m}{(\log m)^2}m^3.\] As reported in [AlRo05] Sudakov has observed that the $\log\log m$ in the upper bound can be removed.

See also [553].

The answer is yes, proved by Füredi [Fu91], who proved that \[\mathrm{ex}(n;H_k) \ll (kn)^{3/2}.\] This was improved to \[\mathrm{ex}(n;H_k) \ll kn^{3/2}\] by Alon, Krivelevich, and Sudakov [AKS03].

Since each $H_k$ is 2-degenerate this is a special case of [146].

A quantity first considered by Moon and Moser [MoMo65], who proved \[n-\log_2n-2\log\log n<g(n)\leq n-\lfloor \log_2 n\rfloor.\] Erdős [Er66b] improved the lower bound to \[n-\log_2 n-\log_*(n)-O(1)<g(n)\] and conjectured this was the correct order of magnitude.

This was disproved by Spencer [Sp71], who proved that in fact \[g(n) > n-\log_2 n-O(1).\]

See also [775].

A problem of Erdős and Nešetřil. Erdős [Er88] wrote 'This problem seems to be interesting only if there is a nice expression for $h_t(d)$.'

It is easy to see that $h_t(d)\leq 2d^t$ always and $h_1(d)=d+1$.

Erdős and Nešetřil and Bermond, Bond, Paoli, and Peyrat [BBPP83] independently conjectured that $h_2(d) \leq \tfrac{5}{4}d^2+1$, with equality for even $d$. This was proved by Chung, Gyárfás, Tuza, and Trotter [CGTT90].

Cambie, Cames van Batenburg, de Joannis de Verclos, and Kang [CCJK22] conjectured that \[h_3(d) \leq d^3-d^2+d+2,\] with equality if and only if $d=p^k+1$ for some prime power $p^k$, and proved that $h_3(3)=23$. They also conjecture that, for all $t\geq 3$, $h_t(d)\geq (1-o(1))d^t$ for infinitely many $d$ and $h_t(d)\leq (1+o(1))d^t$ for all $d$ (where the $o(1)$ term $\to 0$ as $d\to \infty$).

The same authors prove that, if $t$ is large, then there are infinitely many $d$ such that $h_t(d) \geq 0.629^td^t$, and that for all $t\geq 1$ we have \[h_t(d) \leq \tfrac{3}{2}d^t+1.\]

A graph $G$ with chromatic number $k$ in which every vertex is critical is called $k$-vertex-critical.

This was conjectured by Dirac in 1970 for $k\geq 4$ and $r=1$. Dirac's conjecture was proved, for $k=5$, by Brown [Br92]. Lattanzio [La02] proved there exist such graphs for all $k$ such that $k-1$ is not prime. Independently, Jensen [Je02] gave an alternative construction for all $k\geq 5$. The case $k=4$ and $r=1$ remains open.

Martinsson and Steiner [MaSt25] proved this is true for every $r\geq 1$ if $k$ is sufficiently large, depending on $r$.

This is Problem 91 in the graph problems collection.