Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
If \(G\) is an edge-disjoint union of \(n\) copies of \(K_n\), then is \(\chi(G) = n\)?
Let \(\epsilon > 0\) and let \(n\) be sufficiently large depending on \(\epsilon\). Is there a graph on \(n\) vertices with at least \(n^2/8\) many edges which contains no \(K_4\), such that the largest independent set has size at most…
Can every triangle-free graph on \(5n\) vertices be made bipartite by deleting at most \(n^2\) edges?
Does every triangle-free graph on \(5n\) vertices contain at most \(n^5\) copies of \(C_5\)? 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,…
If \(G\) is a graph with infinite chromatic number and \(a_1 < a_2 < \cdots\) are lengths of the odd cycles of \(G\) then \(\sum \frac{1}{a_i} = \infty\). Conjectured by Erdős and Hajnal [ErHa66], and solved by Liu and Montgomery [LiMo20].…
If \(G\) is a graph which contains odd cycles of \(\leq k\) different lengths then \(\chi(G)\leq 2k+2\), with equality if and only if \(G\) contains \(K_{2k+2}\). Conjectured by Bollobás and Erdős. Proved by Gyárfás [Gy92].
Does every graph on \(n\) vertices with \(>\mathrm{ex}(n;C_4)\) edges contain \(\gg n^{1/2}\) many copies of \(C_4\)?
The Erdős–Hajnal Conjecture states that there is a constant \(c(H) > 0\) for each \(H\) such that we can take \(f(n) = n^{c(H)}\) in the above formulation.
Does every graph with infinite chromatic number contain a cycle of length \(2^n\) for infinitely many \(n\)? Conjectured by Mihók and Erdős. Solved affirmatively following the work of Liu and Montgomery [LiMo20]. The linked formal proof…
Does every finite graph with minimum degree at least \(3\) contain a cycle of length \(2^k\) for some \(k \geq 2\)?
Let \(G\) be a graph with \(n\) vertices and \(kn\) edges, and \(a_1<a_2<\cdots\) be the lengths of cycles in \(G\). Assume \(n>0\). Is it true that \[\sum\frac{1}{a_i}\gg \log k?\] Gyárfás, Komlós, and Szemerédi [GKS84] have proved that…
**Erdős Problem 70**: Let \(\mathfrak{c}\) be the order type of the real numbers, let \(\beta\) be a countable ordinal, and let \(2 \le n < \omega\). Is it true that \(\mathfrak{c} \to (\beta, n)^3_2\)? Note: The cases \(n \le 3\) are…
Is it true that for every infinite arithmetic progression \(P\) which contains even numbers there is some constant \(c=c(P)\) such that every graph with average degree at least \(c\) contains a cycle whose length is in \(P\)? In [Er82e]…
Is there a set \(A\subset \mathbb{N}\) of density \(0\) and a constant \(c>0\) such that every graph on sufficiently many vertices with average degree \(\geq c\) contains a cycle whose length is in \(A\)? Bollobás [Bo77] proved that such a…
Let \(k\ge 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\ge (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) be the union of a bipartite graph and \(O_k(1)\) many…
Let \(f(n)\to \infty\) possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on \(n\) vertices can be made bipartite by deleting at most \(f(n)\) edges? The answer is no. A machine-checked…
Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then find the value of \[\lim_{k\to \infty}R(k)^{1/k}.\] This problem is #3…
Let \(R(k)\) be the Ramsey number for \(K_k\). Give a constructive proof that \(R(k) > C^k\) for some constant \(C > 1\). Equivalently, give an explicit construction of graphs on \(n\) vertices which contain no clique and no independent…
We say \(G\) is Ramsey size linear if \(R(G,H)\ll m\) for all graphs \(H\) with \(m\) edges and no isolated vertices. Are there infinitely many graphs \(G\) which are not Ramsey size linear but such that all of its proper subgraphs are?…
Let \(c>0\) and let \(f_c(n)\) be the maximal \(m\) such that every graph \(G\) with \(n\) vertices and at least \(cn^2\) edges, where each edge is contained in at least one triangle, must contain a book of size \(m\), that is, an edge…
Let \(G\) be a chordal graph on \(n\) vertices - that is, \(G\) has no induced cycles of length greater than \(3\). Can the edges of \(G\) be partitioned into \(n^2/6+O(n)\) many cliques?
\(F(n) / \log n \to \infty as n \to \infty\)
Is it true that, for all large \(n\), \(f(n + 1) \ge f(n)\)?
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that every subgraph of \(Q_n\) with \[\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}\] many edges contains a \(C_4\)?
Let \(0 < \epsilon < 1\). Is it true that, if \(k\) is sufficiently large, then \[R(G) > (1-\epsilon)^k R(k)\] for every graph \(G\) with chromatic number \(\chi(G)=k\)? The restriction \(\epsilon < 1\) excludes negative bases in…
For any \(\epsilon>0\) there exists \(\delta=\delta(\epsilon)>0\) such that if \(G\) is a graph on \(n\) vertices with no independent set or clique of size \(\geq \epsilon\log n\) then \(G\) contains an induced subgraph with \(m\) edges…
For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?
If \(G\) is bipartite then \(\mathrm{ex}(n;G)\ll n^{3/2}\) if and only \(G\) is \(2\)-degenerate, that is, \(G\) contains no induced subgraph with minimal degree at least 3. Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered…
Let \(f(m)\) be maximal such that every graph with \(m\) edges must contain a bipartite graph with \[\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)\] edges. Is there an infinite sequence of \(m_i\) such that \(f(m_i)\to \infty\)?…
Let G be a graph with n vertices such that every induced subgraph on ≥ \(n/2\) vertices has more than \(n^2/50\) edges. Must G contain a triangle?
ambiguous statement
Let \(A\subset\mathbb{R}^2\) be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in \(A\), where two vertices are joined by an edge if and only if they are…
Let \(f(n)\) be minimal such that every triangle-free graph \(G\) with \(n\) vertices and diameter \(2\) contains a vertex with degree \(\geq f(n)\). What is the order of growth of \(f(n)\)? Does \(f(n)/\sqrt{n}\to \infty\)? Asked by Erdős…
Let \(\epsilon,\delta>0\) and \(n\) be sufficiently large in terms of \(\epsilon\) and \(\delta\). Let \(G\) be a triangle-free graph on \(n\) vertices with maximum degree \(<n^{1/2-\epsilon}\). Can \(G\) be made into a triangle-free graph…
Let \(f(n)\) be the smallest number of colours required to colour the edges of \(K_n\) such that every \(K_4\) contains at least \(5\) colours. Determine the size of \(f(n)\). Asked by Erdős and Gyárfás [Er97b], who proved…
If \(H\) is bipartite and is \(r\)-degenerate, that is, every induced subgraph of \(H\) has minimum degree \(\leq r\), then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\] The answer is no. OpenAI [OpenAI26] give a connected bipartite 2-degenerate H…
If \(H\) is bipartite with minimum degree \(r\) then there exists \(\epsilon=\epsilon(H)>0\) such that \[\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.\] Conjectured by Erdős and Simonovits [ErSi84]. A probabilistic argument shows that…
A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let \(c(n)\) be the maximum number of minimal cuts a graph on \(n\) vertices can have. Does \(c(n)^{1/n}\to \alpha\) for some \(\alpha <2\)? It is…
For a graph \(G\), let \(\tau(G)\) denote the minimal number of vertices that include at least one from each maximal clique of \(G\) on at least two vertices. Let \(H(n)\) be maximal such that every triangle-free graph on \(n\) vertices…
There exists some constant \(c>0\) such that \[R(C_4,K_n) \ll n^{2-c}.\] The prize of $100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
Burr-Erdős conjecture
The Burr-Erdős conjecture: For any \(d\geq 1\) if \(H\) is a graph such that every subgraph contains a vertex of degree at most \(d\) then \[R(H)\ll_d n.\] Solved by Lee [Le17], who proved that \(R(H) \leq 2^{2^{O(d)}}n\). This problem is…
Prove that \[R(4,k) \gg \frac{k^3}{(\log k)^{O(1)}}.\] This is true, and was proved by Mattheus and Verstraëte [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…
If \(\mathcal{F}\) is a finite set of finite graphs then \(\mathrm{ex}(n;\mathcal{F})\) is the maximum number of edges a graph on \(n\) vertices can have without containing any subgraphs from \(\mathcal{F}\). Note that it is trivial that…
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Prove that \[R(Q_n) \ll 2^n.\]
Let \(R(3;k)\) be the minimal \(n\) such that if the edges of \(K_n\) are coloured with \(k\) colours then there must exist a monochromatic triangle. Determine \[\lim_{k\to \infty}R(3;k)^{1/k}.\] There is no finite limit:…
Any graph on \(n\) vertices can be decomposed into \(O(n)\) many edge-disjoint cycles and edges. This was proved by an internal OpenAI model in September 2026 [OAI26a]; see the linked Lean proof.
We say \(H\) is a unique subgraph of \(G\) if there is exactly one way to find \(H\) as a subgraph (not necessarily induced) of \(G\). Is there a graph on \(n\) vertices with \[\gg \frac{2^{\binom{n}{2}}}{n!}\] many distinct unique…
What is \(\mathrm{ex}_3(n,K_4^3)\)? That is, the largest number of \(3\)-edges which can placed on \(n\) vertices so that there exists no \(K_4^3\), a set of 4 vertices which is covered by all 4 possible \(3\)-edges. See also…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_5\) and at least \(\delta n^2\) edges, must \(G\) contain a set of \(\gg_\delta n\) vertices spanning no triangle? Equivalently, writing…
Show that \[R(3,k+1)-R(3,k)\to\infty\] as \(k\to \infty\). A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
Let \(m\) be sufficiently large and let \(G\) be a graph with \(m\) edges and no isolated vertices. Is the Ramsey number \(R(G)\) maximised when \(G\) is 'as complete as possible'? That is, if \(m=\binom{n}{2}+t\) edges with…
Let \(G\) be a graph with no isolated vertices and \(m\) edges. Is it true that \[R(G) \leq 2^{O(m^{1/2})}?\] This is true, and was proved by Sudakov [Su11]. This problem is #11 in Ramsey Theory in the graphs problem collection.
If \(T\) is a tree on \(n\) vertices then \[R(T) \leq 2n-2.\] This problem is #14 in Ramsey Theory in the graphs problem collection. Solved: the bound follows from the Erdős–Sós theorem (Erdős problem 548) by the pigeonhole principle, as…
Let \(n\geq k+1\). Every graph on \(n\) vertices with at least \(\frac{k-1}{2}n+1\) edges contains every tree on \(k+1\) vertices.
If \(T\) is a tree which is a bipartite graph with \(k\) vertices in one class and \(2k\) vertices in the other class then \[R(T)=4k-1.\] This is false: Norin, Sun, and Zhao [NSZ16] have proved that if \(T\) is the union of two stars on…
Let \(m_1\leq\cdots\leq m_k\) and \(n\) be sufficiently large. If \(T\) is a tree on \(n\) vertices and \(G\) is the complete multipartite graph with vertex class sizes \(m_1,\ldots,m_k\) then prove that \[R(T,G)\leq…
Prove that \[R(C_k,K_n)=(k-1)(n-1)+1\] for \(k\geq n\geq 3\) (except when \(n=k=3\)). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
Determine the Ramsey number \[R(C_4, S_n),\] where \(S_n=K_{1,n}\) is the star on \(n+1\) vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
Let \(R_k(G)\) be the least \(m\) such that every \(k\)-colouring of the edges of \(K_m\) contains a monochromatic copy of \(G\). Determine \(R_k(C_{2n})\).
Erdős Problem 556 (Bondy–Erdős): for all \(n \ge 4\), \[R(C_n; 3) \le 4n - 3.\] The case \(n = 3\) is excluded since \(R(K_3; 3) = 17\).
Let \(R_k(G)\) denote the minimal \(m\) such that if the edges of \(K_m\) are \(k\)-coloured then there is a monochromatic copy of \(G\). Is it true that \[R_k(T)\leq kn+O(1)\] for any tree \(T\) on \(n\) vertices? The answer is yes, with…
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges that is Ramsey for \(G\). If \(G\) has \(n\) vertices and maximum degree \(d\) then prove that…
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges such that in any \(2\)-colouring of the edges of \(H\) there is a monochromatic copy of \(G\). Determine…
F(s,n) is the disjoint union of the stars \(K_{1,n_i}\). The vertex \((i,0)\) is the center of component \(i\); its other \(n_i\) vertices are leaves. -/ local notation "F(" s ", " n ")" => fromRel (fun (u v : Σ i : Fin s, Fin (n i + 1)) ↦…
Let \(R_r(n)\) denote the \(r\)-uniform hypergraph Ramsey number: the minimal \(m\) such that if we \(2\)-colour all edges of the complete \(r\)-uniform hypergraph on \(m\) vertices then there must be some monochromatic copy of the…
Let \(F(n,\alpha)\) denote the smallest \(m\) such that there exists a \(2\)-colouring of the edges of \(K_n\) so that every \(X\subseteq [n]\) with \(\lvert X\rvert\geq m\) contains more than \(\alpha \binom{\lvert X\rvert}{2}\) many…
Let \(R_3(n)\) be the minimal \(m\) such that if the edges of the \(3\)-uniform hypergraph on \(m\) vertices are \(2\)-coloured then there is a monochromatic copy of the complete \(3\)-uniform hypergraph on \(n\) vertices. Is there some…
Let \(G\) be such that any subgraph on \(k\) vertices has at most \(2k-3\) edges. Is it true that, if \(H\) has \(m\) edges and no isolated vertices, then \(R(G,H) \ll m\)? In other words: if \(G\) is sparse (every induced subgraph on…
**Erdős Problem 567 (Q3)** Is \(Q_3\) (the 3-dimensional hypercube) Ramsey size linear?
Let \(G\) be a graph such that \(R(G,T_n)\ll n\) for any tree \(T_n\) on \(n\) vertices and \(R(G,K_n)\ll n^2\). Is it true that, for any \(H\) with \(m\) edges and no isolated vertices, \[R(G,H)\ll m?\] In other words, is \(G\) Ramsey…
Let \(k\geq 1\). What is the best possible \(c_k\) such that \[R(C_{2k+1},H)\leq c_k m\] for any graph \(H\) on \(m\) edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
Let \(k\geq 3\). Is it true that, if \(m\) is sufficiently large, for any graph \(H\) on \(m\) edges without isolated vertices, \[R(C_k,H) \leq 2m+\left\lfloor\frac{k-1}{2}\right\rfloor?\] This was proved for even \(k\) by Erdős, Faudree,…
Show that for any rational \(\alpha \in [1,2)\) there exists a bipartite graph \(G\) such that \[\mathrm{ex}(n;G)\asymp n^{\alpha}.\] The proof constructs balanced rooted models for all rational parameters. Its upper-bound closure replaces…
Show that for \(k\geq 3\) \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.\] This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Is it true that \[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\] A problem of Erdős and Simonovits. This problem is asking whether the threshold is the same as for forbidding \(C_4\) and all odd cycles (see erdos_573.variants.kst) if one…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_{2,2,2}\) (the octahedron) and at least \(\delta n^2\) edges, must \(G\) contain an independent set of size \(\gg_\delta n\)? This is a…
Let \(f(m)\) be the maximal \(k\) such that a triangle-free graph on \(m\) edges must contain a bipartite graph with \(k\) edges. Determine \(f(m)\). Resolved by Alon [Al96], who showed that there exist constants \(c_1,c_2>0\) such that…
Does there exist a graph \(G\) which contains no \(K_4\), and yet any \(2\)-colouring of the edges produces a monochromatic \(K_3\)? Erdős and Hajnal [ErHa67] first asked for the existence of any such graph. Existence was proved by Folkman…
Every connected graph on \(n\) vertices can be partitioned into at most \(\lceil n/2\rceil\) edge-disjoint paths. A problem of Erdős and Gallai.
**Erdős Problem 593 (\\(500)**: Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number \)> \aleph_0…
**Erdős Problem 594** (Erdős–Hajnal [ErHa66], [Er69b]): Does every graph \(G\) with chromatic number \(\geq \aleph_1\) contain all sufficiently large odd cycles? The answer is **Yes**, proved by Erdős, Hajnal, and Shelah [EHS74]. A graph…
**Erdős Problem 595 (\\(250)**: Is there an infinite graph \)G\( which contains no \)K_4$ and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
**Erdős Problem 596** (Erdős–Hajnal, [Er87]). For which graph pairs \((G_1, G_2)\) is it true that (1) for every \(n \geq 1\) there is a graph \(H\) without a \(G_1\) such that any \(n\)-colouring of \(H\)'s edges contains a monochromatic…
Erdős-Menger conjecture
**Erdős Problem 599** (the Erdős–Menger conjecture). Let \(G\) be a (possibly infinite) graph and let \(A, B\) be disjoint independent sets of vertices. Must there exist a family \(P\) of pairwise vertex-disjoint paths from \(A\) to \(B\),…
Let \(r \geq 2\). Is it true that \(e(n,r+1) - e(n,r) \to \infty\) as \(n \to \infty\)?
Let \(f(n)\) be the minimal \(m\) such that if the edges of \(K_{2^n+1}\) are coloured with \(n\) colours then there must be a monochromatic odd cycle of length at most \(m\). Estimate \(f(n)\).
**Erdős Problem 613:** Let \(n \geq 3\) and \(G\) be a graph with \(\binom{2n+1}{2} - \binom{n}{2} - 1\) edges. Must \(G\) be the union of a bipartite graph and a graph with maximum degree less than \(n\)?
Let \(f(n,k)\) be minimal such that there is a graph with \(n\) vertices and \(f(n,k)\) edges where every set of \(k+2\) vertices induces a subgraph with maximum degree at least \(k\). Determine \(f(n,k)\).
Does there exist some constant \(c > 0\) such that for all sufficiently large \(n\), if \(G\) is a graph with \(n\) vertices and at least \((1/8 - c)n^2\) edges then \(G\) must contain either a \(K_4\) or an independent set on at least…
Let \(r\geq 3\). For an \(r\)-uniform hypergraph \(G\) let \(\tau(G)\) denote the covering number (or transversal number), the minimum size of a set of vertices which includes at least one from each edge in \(G\). Determine the best…
Let \(r\geq 3\). If the edges of \(K_{r^2+1}\) are \(r\)-coloured then there exist \(r+1\) vertices with at least one colour missing on the edges of the induced \(K_{r+1}\). In other words, there is no balanced colouring. A conjecture of…
For a triangle-free graph \(G\) let \(h_2(G)\) be the smallest number of edges that need to be added to \(G\) so that it has diameter \(2\) and is still triangle-free. Is it true that if \(G\) has maximum degree \(o(n^{1/2})\) then…
**Erdős Problem 619** [EGR98, Er99]: For a triangle-free graph \(G\) let \(h_r(G)\) be the smallest number of edges that need to be added to \(G\) so that it has diameter \(r\) (while preserving the property of being triangle-free). Is it…
Erdős-Rogers problem
Let \(G\) be a graph on \(n\) vertices, \(\alpha_1(G)\) be the maximum number of edges that contain at most one edge from every triangle, and \(\tau_1(G)\) be the minimum number of edges that contain at least one edge from every triangle.…
Let \(k \geq 4\) and let \(g_k(n)\) denote the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) and girth \(> m\) (i.e. containing no cycle of length \(\leq m\)). Does…
Let \(\omega(G)\) denote the clique number of \(G\) and \(\chi(G)\) the chromatic number. If \(f(n)\) is the maximum value of \(\chi(G)/\omega(G)\), as \(G\) ranges over all graphs on \(n\) vertices, then does…
Erdős-Lovász Tihany Conjecture
Let \(G\) be a graph with chromatic number \(k\) containing no \(K_k\). If \(a,b\geq 2\) and \(a+b=k+1\) then must there exist two disjoint subgraphs of \(G\) with chromatic numbers \(\geq a\) and \(\geq b\) respectively?
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
Suppose \(G\) is a graph on \(n\) vertices which contains no complete graph or independent set on \(\gg \log n\) many vertices. Must \(G\) contain \(\gg n^{5/2}\) induced subgraphs which pairwise differ in either the number of vertices or…
Is it true that if the edges of \(K_n\) are 2-coloured then there are at most \(n^2/4\) many edges which do not occur in a monochromatic triangle? Solved by Erdős, Rousseau, and Schelp for large \(n\), but unpublished. Alon has observed…
For every \(k \geq 3\), does there exist \(f(k)\) such that every finite graph of chromatic number at least \(f(k)\) has an odd cycle whose vertices induce a graph of chromatic number at least \(k\)? The cycle may have chords in the…
Is there some function \(f\) such that for all \(k\geq 1\) if a finite graph \(G\) has chromatic number \(\geq f(k)\) then \(G\) has \(k\) edge disjoint cycles on the same set of vertices? A problem of Erdős and Hajnal. This was resolved…
Let \(f(n)\) be the maximal number of edges in a graph on \(n\) vertices such that all cycles have more vertices than chords. Is it true that \(f(n)\ll n\)? A problem of Hamburger and Szegedy. A chord is an edge between two vertices of the…
Let \(f(n;t)\) be minimal such that if a \(t\)-uniform hypergraph on \(n\) vertices contains at least \(f(n;t)\) edges then there must be four edges \(A,B,C,D\) such that \[A\cup B= C\cup D\] and \[A\cap B=C\cap D=\emptyset.\] Estimate…
Let \(Q_n\) be the \(n\)-dimensional hypercube graph (so that \(Q_n\) has \(2^n\) vertices and \(n2^{n-1}\) edges). Is it true that, for every \(\epsilon>0\), if \(n\) is sufficiently large, every subgraph of \(Q_n\) with \[\geq \epsilon…
Let \(p, q \geq 1\) be fixed integers. Define \(H(n) = H(n; p, q)\) to be the largest \(m\) such that any graph on \(n\) vertices where every set of \(p\) vertices spans at least \(q\) edges must contain a complete graph on \(m\) vertices.…
Does \(\chi(G_n)\) grow exponentially in \(n\)? Yes: Frankl and Wilson [FrWi81] proved an exponential lower bound and Larman and Rogers [LaRo72] proved an exponential upper bound. Here exponential growth means that there are constants…
Let \(G\) be a finite unit distance graph in \(\mamthbb{R}^2\). Is there some \(k\) such that if \(G\) has girth \(≥ k\), then \(\chi(G) ≤ 3\)? The general case was solved by O'Donnell [OD99], who constructed finite unit distance graphs…
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there…
Is it true that, for every bipartite graph \(G\), there exists some \(\alpha\in [1,2)\) and \(c>0\) such that \[\mathrm{ex}(n;G)\sim cn^\alpha?\] The condition that \(G\) have at least two edges excludes degenerate forbidden graphs whose…
Is it true that \[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]
Ruzsa-Szemerédi problem
Let \(\mathcal{F}\) be the family of all \(3\)-uniform hypergraphs with \(6\) vertices and \(3\) \(3\)-edges. Is it true that \[\mathrm{ex}_3(n,\mathcal{F})=o(n^2)?\] The answer is yes, proved by Ruzsa and Szemerédi [RuSz78] (this is known…
Let \(r\geq 2\), and let \(\mathrm{ex}_r(n;K_{r+1}^r)\) be the maximum number of \(r\)-edges that can be placed on \(n\) vertices without forming a \(K_{r+1}^r\) (the \(r\)-uniform complete graph on \(r+1\) vertices). Is every…
Let \(\hat{R}(G)\) denote the size Ramsey number, the minimal number of edges \(m\) such that there is a graph \(H\) with \(m\) edges such that in any \(2\)-colouring of the edges of \(H\) there is a monochromatic copy of \(G\). Is it true…
Let \(\mathfrak{m}\) be an infinite cardinal and \(G\) be a graph with chromatic number \(\mathfrak{m}\). Let \(r\geq 1\). Must \(G\) contain a subgraph of chromatic number \(\mathfrak{m}\) which does not contain any odd cycle of length…
**Murty-Simon Conjecture** Let \(G\) be a graph on \(n\) vertices with diameter \(2\) such that deleting any edge increases the diameter. Is it true that \(G\) has at most \(\lfloor n^2 / 4 \rfloor\) edges? Equality is conjectured to hold…
tree packing conjecture
Let \(T_2,\ldots,T_n\) be a collection of trees such that \(T_k\) has \(k\) vertices. Can we always write \(K_n\) as the edge disjoint union of the \(T_k\)? A conjecture of Gyárfás, known as the tree packing conjecture. We state it as a…
Let \(f(m)\) be some function such that \(f(m)\to \infty\) as \(m\to \infty\). Does there exist a graph \(G\) of infinite chromatic number such that every subgraph on \(m\) vertices contains an independent set of size at least…
Let \(G\) be a graph with chromatic number \(\chi(G)=4\). If \(m_1<m_2<\cdots\) are the lengths of the cycles in \(G\) then can \(\min(m_{i+1}-m_i)\) be arbitrarily large? The answer is no: Bondy and Vince [BoVi98] proved that every graph…
The list chromatic number \(\chi_L(G)\) is defined to be the minimal \(k\) such that for any assignment of a list of \(k\) colours to each vertex of \(G\) (perhaps different lists for different vertices) a colouring of each vertex by a…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or independent set. If \(G\) is a graph with…
The cochromatic number of \(G\), denoted by \(\zeta(G)\), is the minimum number of colours needed to colour the vertices of \(G\) such that each colour class induces either a complete graph or empty graph. Is it true that if \(G\) has no…
Give an asymptotic formula for \(\mathrm{ex}(n; C_4)\). Erdős and Klein [Er38] proved \(\mathrm{ex}(n; C_4) \asymp n^{3/2}\), and Reiman [Re58] proved \[\frac{1}{2\sqrt 2} \le \lim \frac{\mathrm{ex}(n; C_4)}{n^{3/2}} \le \frac12.\] Erdős…
Let \(f(n;k,l)=\min \mathrm{ex}(n;G)\), where \(G\) ranges over all graphs with \(k\) vertices and \(l\) edges. Give good estimates for \(f(n;k,l)\) in the range \(k<l\leq k^2/4\). In [Er64c, p. 33] this question is asked for…
Let \(g_k(n)\) be the maximal number of edges possible on a graph with \(n\) vertices which does not contain a cycle with \(k\) chords incident to a vertex on the cycle. Is it true that \[g_k(n)=(k+1)n-(k+1)^2\] for \(n\) sufficiently…
Is there a \(3\)-uniform hypergraph on \(n\) vertices which contains at least \(n-O(1)\) different sizes of cliques (maximal complete subgraphs)? The answer is no, as proved by Gao [Ga25]: more generally, for any \(k\geq 3\), every…
Is it true that every \(3\)-uniform hypergraph on \(3n\) vertices with at least \(n^3+1\) edges must contain either a subgraph on \(4\) vertices with \(3\) edges or a subgraph on \(5\) vertices with \(7\) edges? Harris has provided the…
If \(G\) is a graph on \(n\) vertices which has no two adjacent vertices of degree \(\geq 3\) then \[R(G)\ll n,\] where the implied constant is absolute. A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94].
If \(G\) is a graph on \(n\) vertices containing no independent set on \(>n^{1/2}\) vertices then there is a set of \(\leq n^{1/2}\) vertices containing \(\gg n^{1/2}\log n\) edges. Proved by Alon [Al96b].
Is it true that any \(K_r\)-free graph on \(n\) vertices with average degree \(t\) contains an independent set on \[\gg_r \frac{\log t}{t}n\] many vertices? A conjecture of Ajtai, Erdős, Komlós, and Szemerédi [AEKS81].
We call a graph \(H\) \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree of \(H\) is at most \(D\) times the minimum degree of \(H\). Is it true that for every \(m\geq 1\), if \(n\) is sufficiently large, any graph on \(n\)…
Let \(f(m,n)\) be maximal such that any graph on \(n\) vertices in which every induced subgraph on \(m\) vertices has an independent set of size at least \(\log n\) must contain an independent set of size at least \(f(n)\). Estimate…
Does there exist some \(\epsilon>0\) such that, for all sufficiently large \(n\), there exists a graph \(G\) on \(n\) vertices with at least \(\epsilon n^2\) edges whose edges can be coloured with \(n\) colours so that every \(C_4\)…
\(R(n)\) denotes the diagonal Ramsey number \(R(n,n)\), i.e., hypergraphRamsey 2 n. -/ local notation "R" => hypergraphRamsey 2 /-- Is it true that \(\frac{R(n+1)}{R(n)}\geq 1+c\) for some constant \(c>0\), for all large \(n\)?
Let \(h(n)\) be minimal such that every graph on \(n\) vertices where every set of \(7\) vertices contains a triangle must contain a clique on at least \(h(n)\) vertices. Estimate \(h(n)\). In particular, do there exist constants…
Let \(k\geq 2\) and \(G\) be a graph with \(n\geq k-1\) vertices and \[(k-1)(n-k+2)+\binom{k-2}{2}+1\] edges. Does there exist some \(c_k>0\) such that \(G\) must contain an induced subgraph on at most \((1-c_k)n\) vertices with minimum…
Let \(G\) be a graph with \(2n+1\) vertices and \(n^2+n+1\) edges. Must \(G\) contain two vertices of the same degree which are joined by a path of length \(3\)? A problem of Erdős and Hajnal. The example of \(K_{n,n+1}\) shows that this…
Let \(r\geq 3\) and \(k\) be sufficiently large in terms of \(r\). Is it true that every \(r\)-uniform hypergraph with chromatic number \(k\) has at least \[\binom{(r-1)(k-1)+1}{r}\] edges, with equality only for the complete graph on…
Does there exist an absolute constant \(c>0\) such that, for all \(r\geq 2\), in any \(r\)-uniform hypergraph with chromatic number \(3\) there is a vertex contained in at least \((1+c)^r\) many edges? This was solved by Erdős and Lovász…
Does there exist a \(3\)-critical \(3\)-uniform hypergraph in which every vertex has degree \(\geq 7\), where criticality means that the transversal number is \(3\) and deleting any edge reduces it to \(2\)? In the first formulation, the…
Does there exist a \(k>2\) such that the \(k\)-sized subsets of {1,...,2k} can be coloured with \(k+1\) colours such that for every \(A\subset \{1,\ldots,2k\}\) with \(\lvert A\rvert=k+1\) all \(k+1\) colours appear among the \(k\)-sized…
Let \(r\geq 2\) and let \(G\) be an intersecting \(r\)-uniform hypergraph with chromatic number \(3\). Must \(G\) contain \(O(r^2)\) many vertices? Vertices are counted in the union of the edges, so isolated vertices are excluded. Alon has…
Let \(k\geq 2\) and \(A_k\subseteq [0,1]\) be the set of \(\alpha\) such that there exists some \(\beta(\alpha)>\alpha\) with the property that, if \(G_1,G_2,\ldots\) is a sequence of \(k\)-uniform hypergraphs with \[\liminf…
Let \(G\) be a graph on \(3n\) vertices formed by taking \(n\) vertex disjoint triangles and adding a Hamiltonian cycle (with all new edges) between these vertices. Does \(G\) have chromatic number at most \(3\)? The answer is yes, proved…
For \(A\subseteq \{1,\ldots,n\}\) let \(G(A)\) be the graph with vertex set \(A\), where two integers are joined by an edge if they are coprime. Is it true that if \[|A| > \lfloor n/2 \rfloor + \lfloor n/3 \rfloor - \lfloor n/6 \rfloor\]…
Is it true that, for all sufficiently large \(n\), if \(G\) is a triangle-free graph on \(\{1,\ldots,n\}\) then there must exist three independent points \(a,b,a+b\)? A problem of Erdős and Hajnal [Er95d]. The stated problem has been…
Let \(f(n)\) be minimal such that there is a tournament (a complete directed graph) on \(f(n)\) vertices such that every set of \(n\) vertices is dominated by at least one other vertex. Estimate \(f(n)\).
Let \(r\geq 2\) and let \(t_r(n)\) be the Turán number (the maximal number of edges in a graph on \(n\) vertices with no \(K_{r+1}\)). If \(G\) is a graph with \(n\) vertices and \(m\geq t_r(n)\) edges there exists a clique on \(r\)…
Every graph with \(n\) vertices and \(>n^2/4\) edges contains an edge which is in at least \(n/6\) triangles. A conjecture of Bollobás and Erdős. This was proved independently by Edwards (unpublished) and Khadzhiivanov and Nikiforov…
Let \(r\geq 2\) and \(m\geq 1\). Every graph with \(rm\) vertices and minimum degree at least \(m(r-1)\) contains \(m\) vertex disjoint copies of \(K_r\). When \(r=2\) this follows from Dirac's theorem. Corrádi and Hajnal [CoHa63] proved…
Let \(G\) be a graph with \(1+n(m-1)\) vertices and \(1+n\binom{m}{2}\) edges. Must \(G\) contain two points which are connected by \(m\) disjoint paths? A conjecture of Bollobás and Erdős [BoEr62]. This would be the best possible, as…
Is it true that, for \(k\geq 4\), \(f_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}}\) for some constant \(c_k>0\)? This problem follows immediately from Mattheus and Verstraete's lower bound [MaVe23] for k = 4 and Bradač's lower…
Let \(k\geq 4\) and let \(f_k(n)\) be the largest \(m\) such that there is a graph on \(n\) vertices with chromatic number \(k\) in which every odd cycle has length \(> m\). Then \[f_k(n) \asymp n^{\frac{1}{k-2}}.\] A question of Erdős and…
Let \(k\geq 0\). Let \(G\) be a graph such that every subgraph \(H\) contains an independent set of size \(\geq (n-k)/2\), where \(n\) is the number of vertices of \(H\). Must \(G\) have chromatic number at most \(k+2\)? A question of…
Is it true that, for every \(k\), there is some \(f(k)\) such that if \(G\) has chromatic number \(\geq f(k)\) then \(G\) contains a triangle-free subgraph with chromatic number \(\geq k\)? This is true, as shown by Rödl [Ro77].
Let \(k\geq 4\). Is it true that \[\mathrm{ex}(n;H_k) \ll_k n^{3/2},\] where \(H_k\) is the graph on vertices \(x,y_1,\ldots,y_k,z_1,\ldots,z_{\binom{k}{2}}\), where \(x\) is adjacent to all \(y_i\) and each pair of \(y_i,y_j\) is adjacent…
Let \(g(n)\) be the maximum number of different sizes of cliques that can occur in a graph on \(n\) vertices. Estimate \(g(n)\) - in particular, is it true that \[g(n) = n - \log_2 n - \log_*(n) + O(1),\] where \(\log_*(n)\) is the number…
Let \(k \ge 4\) and \(r\ge 1\). Must there exist a graph \(G\) with chromatic number \(k\) such that every vertex is critical, yet every critical set of edges has size \(>r\)?
For any fixed \(s\geq 3\), \[R(s,k) \gg \frac{k^{s-1}}{(\log k)^c}\] for some constant \(c=c(s)>0\). According to Chung and Graham [ChGr98] this was first conjectured by Erdős in 1947. Proved by Bradač [Br26], with \(c=2s-4\). The linked…
The dimension of a graph \(G\) is the minimal \(n\) such that \(G\) can be embedded in \(\mathbb{R}^n\) such that every edge of \(G\) is a unit line segment. What is the smallest number of edges in a graph with dimension \(4\)? Answer: The…
Does every graph with \(m\) edges contain a subgraph with \(\gg m^{2/3}\) edges which contains no \(C_4\)? This problem was first solved in the affirmative by Conlon, Fox, and Sudakov [CFS14b]. A simple proof is given by Hunter in the…
Is it true that, for every \(c>0\), there exists \(f(c)\) such that every graph on \(n\) vertices with at least \(\lfloor n^2/4\rfloor+k\) edges, where \(k<c n\), contains at least \(k-f(c)\) many edge disjoint triangles? Erdős [Er71]…
Let \(t<\lfloor n/2\rfloor\). Does every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+t\) edges contain at least \(t\lfloor n/2\rfloor\) triangles? Rademacher proved that every graph on \(n\) vertices with \(\lfloor n^2/4\rfloor+1\)…
Let \(R(k,l)\) be the Ramsey number, so the minimal \(n\) such that every graph on at least \(n\) vertices contains either a \(K_k\) or an independent set on \(l\) vertices. Prove, for fixed \(k\geq 3\), that \[\lim_{l\to…
pancyclic graphs
Erdős matching conjecture
Let \(f(n;r,k)\) be the maximal number of edges in an \(r\)-uniform hypergraph which contains no set of \(k\) many independent edges. For all \(r\geq 3\), \[f(n;r,k)=\max\left(\binom{rk-1}{r}, \binom{n}{r}-\binom{n-k+1}{r}\right).\] Note:…
Is it true that, for every \(k \geq 3\), there is a constant \(c_k > 0\) such that \[\mathrm{ex}(n, G_k) \ll n^{3/2 - c_k},\] where \(G_k\) is the bipartite graph between \(\{y_1, \ldots, y_k\}\) and \(\{z_1, \ldots, z_{\binom{k}{2}}\}\),…
Let \(f(n)\) be such that every \(3\)-uniform linear hypergraph on \(n\) vertices contains an independent set on \(f(n)\) vertices. Estimate \(f(n)\). Phelps and Rödl [PhRo86] proved \(f(n) \asymp (n\log n)^{1/2}\).
Let \[H(n)=\min_f \max_{X\subseteq \{1,\ldots,n\}} \left\lvert \sum_{x<y\in X} f(x,y)\right\rvert,\] where \(f\) ranges over all functions \(f:\{1,\ldots,n\}^2\to \{-1,1\}\). Estimate \(H(n)\). Erdős [Er63d] proved \[\frac{n}{4}\leq H(n)…
If \(R(k)\) is the Ramsey number for \(K_k\), the minimal \(n\) such that every \(2\)-colouring of the edges of \(K_n\) contains a monochromatic copy of \(K_k\), then \[\frac{R(k)}{k2^{k/2}}\to \infty.\] In [Er93] Erdős offers…
Let \(R(k,l)\) be the usual Ramsey number: the smallest \(n\) such that if the edges of \(K_n\) are coloured red and blue then there exists either a red \(K_k\) or a blue \(K_l\). Prove the existence of some \(c>0\) such that \[\lim_{k\to…
Let \(h(n)\) be such that every graph on \(n\) vertices with \(>n^2/4\) many edges contains a triangle whose vertices have degrees summing to at least \(h(n)\). Estimate \(h(n)\). In particular, is it true that \[h(n)\geq…
Let \(G\) be a graph on \(n\) vertices with \(>n^2/4\) many edges. Must there be a triangle \(T\) in \(G\) and vertices \(y_1,\ldots,y_t\), where \(t>(\frac{1}{2}-o(1))n\), such that every \(y_i\) is joined to at least two vertices of…
Is there a constant \(c > 0\) such that every graph on \(2^n\) vertices with minimum degree \(> (1-c) \cdot 2^n\) contains the \(n\)-dimensional hypercube \(Q_n\)? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal…
Let \(G\) be a graph on \(n\) vertices which does not contain a trivial (empty or complete) graph on more than \(c\log n\) vertices. Must \(G\) contain at least \(2^{\Omega_c(n)}\) many induced subgraphs which are not pairwise isomorphic?…
Let \(G\) be a graph on \(n\) vertices in which every degree occurs at most twice, and the number of distinct degrees is \(>(\frac{1}{2}+\epsilon)n\). Must \(G\) contain a trivial (empty or complete) subgraph of size 'much larger' than…
Does every graph with chromatic number \(\aleph_1\) contain an infinitely connected subgraph with chromatic number \(\aleph_1\)? Komjáth [Ko13] proved that it is consistent that the answer is no. This was improved by Soukup [So15], who…
Does every graph with chromatic number \(\aleph_1\) contain a countable subgraph which is infinitely connected?
We call a graph \(D\)-balanced (or \(D\)-almost-regular) if the maximum degree is at most \(D\) times the minimum degree. Let \(ε, α > 0\) and \(D\) and \(n\) be sufficiently large. If \(G\) is a graph on \(n\) vertices with at least…
Let \(r\geq 4\). If \(G\) is a graph on \(n\) vertices with at least \(\mathrm{ex}(n;K_r)\) edges then must \(G\) contain a vertex with degree \(d\gg_r n\) whose neighbourhood contains at least \(\mathrm{ex}(d;K_{r-1})\) edges? As Erdős…
Let \(G\) be a bipartite graph on \(n\) vertices such that one part has \(\lfloor n^{2/3}\rfloor\) vertices. Is there a constant \(c>0\) such that if \(G\) has at least \(cn\) edges then \(G\) must contain a \(C_6\)? The answer is no, as…
Is it true that \(f_2(n) \gg n\)? Disproved by Rödl, who showed \(f_r(n) = o(n)\) for all fixed \(r \geq 2\). A conjecture of Erdős, Hajnal, and Szemerédi. This seems to be closely related to, but distinct from,…
The anti-Ramsey number \(\mathrm{AR}(n,G)\) is the maximum possible number of colours in which the edges of \(K_n\) can be coloured without creating a rainbow copy of \(G\) (i.e. one in which all edges have different colours). Let \(C_k\)…
For \(r\geq 3\) let \(d_r(e)\) be the minimal \(d\) such that \[\mathrm{ex}_r(n,\mathcal{F})=o(n^2),\] where \(\mathcal{F}\) is the family of \(r\)-uniform hypergraphs on \(d\) vertices with \(e\) edges. Prove that \[d_r(e)=(r-2)e+3\] for…