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 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\)?
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…
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 \(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…
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?
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.
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.
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 \(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 \(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…
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…
pancyclic graphs