Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
1,221 problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether the measure of reals well approximated by fractions with denominator between N and cN tends to a limit, and what that limit is explicitly.
Asks whether the logarithmically normalized sum of one half minus fractional parts of multiples of a fixed irrational has an asymptotic distribution function.
Asks whether Euler's totient function takes the same value at n and at n plus one for infinitely many n.
Asks whether, for every fixed positive c and all large x, some n up to x has all totient values on an interval of length a power of the logarithm of x distinct.
Estimates f(n), the largest d such that Farey fractions of order n at most d places apart are similarly ordered; asks if f(n) = (c + o(1))n. Marked solved on Cipollini's 2026 preprint (c = 1/4, matching van Doorn's upper bound).
Asks whether every graph of girth at least five has an acyclic orientation that stays acyclic after any one edge is reversed; false, by Nešetřil and Rödl's large-girth graphs with a monotone cycle under every vertex ordering.
The smallest number of edges of a graph of dimension four, the least Euclidean dimension in which it embeds with every edge a unit segment; nine, attained only by K_{3,3} up to isolated vertices, by House and Chaffee-Noble.
Asks whether every graph with m edges has a four-cycle-free subgraph with at least a constant times m^{2/3} edges; true (Conlon, Fox and Sudakov), while Bollobás and Erdős's first form with m^{3/4} fails by Folkman's example.
Asks whether, for each positive c, a graph on n vertices with the Turán number plus k edges, k below cn, has at least k minus f(c) edge-disjoint triangles; proved by Győri (1988), a paper known only by attestation.
Asks whether every graph on n vertices with the Turán number plus t edges, t below half of n, has at least t times the floor of half of n triangles; the Erdős-Rademacher conjecture, proved in full by Lovász and Simonovits.
Determines the least number of edges forcing a triangle in a graph on n vertices whose chromatic number is at least r; known exactly for r up to three, for r equal to four and n large, and open in general.
Determines or estimates how large n must be, in terms of k, for a given edge count to force a cycle through all but k of the n vertices; Woodall's 1972 Corollary 11.1 gives every n at least 2k + 3 and covers the smaller n too.
Asks for an asymptotic formula for the fewest vertices of a triangle-free graph with chromatic number k, and for a proof that consecutive values have ratio tending to one.
Asks whether, for each fixed k, the ratio of consecutive off-diagonal Ramsey numbers R(k,l+1)/R(k,l) tends to one; answered yes by a 2026 manuscript hosted by OpenAI, attributed to an internal model and accepted by the site.
The most vertices a two-colored complete graph can force to be left over when it is covered by disjoint monochromatic copies of K_t; Burr, Erdős and Spencer determine it for fixed t and large n in terms of R(t,t−1), so it grows exponentially.
Estimates the fewest edges beyond n for an n-vertex graph to have cycles of every length from three to n; the excess is at least log_2(n-1) - 1, Bondy claimed log_2 n plus an iterated logarithm, and a 2026 proof claim is pending.
Estimates the number of edge-disjoint complete graphs needed to partition the edges of a graph on n vertices with more than n squared over 4 edges; open; Győri and Keszegh settle the K_4-free case up to about n squared / 16.
Asks whether every large graph with at least n to the power one plus epsilon edges has a non-planar subgraph of bounded size; answered yes by Kostochka and Pyber in 1988 through a bounded subdivided K_5.
Asks whether every graph on n vertices with the Turán number plus half of n edges contains a saturated planar subgraph on more than three vertices; proved by Simonovits in his thesis, attested by Erdős and the site.
Asks whether, for r at least 3 and n at least rk, the most edges in an r-uniform hypergraph on n vertices with no k pairwise disjoint edges is the larger of the clique count and the star count.
Asks whether, for every k at least three, the extremal number of the bipartite graph joining each pair among k vertices to its own vertex beats n to the 1.5.
Asks whether sets of size at least t, few of which lie inside any given set relative to its size, can always be two-colored with no monochromatic member.
Asks whether the largest family of subsets of the first n integers with no member a union of others is a constant times two to the n over the square root of n.
Estimates the largest independent set guaranteed in a three-uniform hypergraph on n vertices in which any two edges share at most one vertex.
Independent sets for a function assigning to each pair from the first n integers a third value, meaning sets closed away from the values of their own pairs.