Problems
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
618 of 1,221 problems match
Every problem posed by Paul Erdős, with its status, references, discussion and proof claims.
Asks whether, in every graph on vertices, the largest edge set containing at most one edge of each triangle and the smallest edge set meeting every triangle have sizes summing to at most .
Asks whether every regular graph of degree on vertices has vertex subsets spanned by a cycle; proved, and the limiting constant is .
Asks whether almost surely for the random graph , where the cochromatic number is the fewest colors whose classes each induce a complete or empty graph.
Asks whether every planar bipartite graph has list chromatic number at most . The list chromatic number is the least list size per vertex that always permits a proper coloring from the lists.
Asks whether every planar graph has list chromatic number at most , and whether is best possible. The list chromatic number is the least list size per vertex that always allows a proper coloring from the lists.
Asks whether every -choosable graph is -choosable for every integer . A graph is -choosable if, from any lists of colors, one can choose colors per vertex so that adjacent vertices get disjoint sets.
Asks which triangles can only be cut into a square number of congruent triangles.
Asks whether a graph on vertices with no large clique or independent set has many induced subgraphs that pairwise differ in vertex count or edge count.
Asks whether a graph on vertices with no large clique or independent set has an induced subgraph on many vertices with many distinct degrees.
Asks whether, for large , every 2-coloring of the edges of leaves at most edges in no monochromatic triangle, as Erdős stated it. Proved by Keevash and Sudakov's exact theorem, though the erdosproblems.com wording fails for .
Asks whether there is a function such that every finite graph with chromatic number at least has edge-disjoint cycles on the same vertex set, for every .
Asks whether every 2-coloring of the positive integers has a monochromatic progression with . Proved by Brown and Landman in 1999, and erdosproblems.com also records an elementary argument.
Asks whether, for any distinct primes , there are infinitely many such that is divisible by an even power of each .
Asks to estimate the length of the longest chain of integers whose greatest prime factors strictly decrease.
Asks whether, for any two primes and , some integer has greatest prime factor while has greatest prime factor .
Asks for the least number of distinct multiples of distinct elements of an -element set that every interval of length contains. By van Doorn, Li and Tang (2026), , so the answer to whether is no.
Asks whether the number of points in general position in needed to guarantee in convex position grows exponentially in .
Asks whether the least possible number of distinct distances from the -th of planar points, in units of , tends to infinity with . Erdős's first guess, that it is unbounded already at , fails by a construction of Elekes.
Asks whether the counts of distinct distances from each of planar points to the others can take different values; yes, by an unrefereed Lean proof that Conjectures.io kernel-checked and certified.
Asks whether every set of positive upper density contains, after some shift, all sums of two distinct members of an infinite subset of .
Asks whether every subset of the grid with at least points contains the four vertices of a square once is large in terms of .
Asks whether planar points can have every four of them determine at least three distances while the number of distinct distances is .
Concerns families of subsets of , each of size above for a constant , in which any two members share at most one element. It asks whether some set meets every member in a nonempty, bounded number of points.
Asks whether, for every and all large , every subgraph of the hypercube with at least an fraction of its edges contains a .
Asks whether the sum of the ratios of consecutive divisors of tends to infinity for almost all , and seeks an asymptotic formula for its average.