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 for which limit ordinals every graph on that many vertices has an infinite path or an independent set whose vertices have that same order type.
Asks whether a family of countably infinite sets meeting pairwise in a finite set of size other than one can always be two-colored with no set monochromatic.
The least number of colors always enough to color the union of countably infinite sets meeting pairwise in a set of size other than two with none one color.
Asks whether any n distinct points in the plane must contain a point from which the number of distinct distances to the others is almost n.
Asks whether n points can be placed on a sphere so that the number of pairs at one repeated distance exceeds any fixed multiple of n as n grows.
Asks which values can occur as the number of distinct lines determined by n distinct points in the plane; determined for all sufficiently large n; the small cases are open.
Asks whether the number of distinct sets of line sizes determined by n points in the plane is at most exp(O(sqrt n)).
Asks whether every graph on n vertices with more than a quarter of n squared edges has at least two ninths of n squared edges lying on five-cycles.
Estimates the least m such that n-coloring a complete graph on two to the n plus one vertices forces a monochromatic odd cycle of length at most m.
Bounds the clique transversal number of an n-vertex graph; proved, with the answer n − Θ(√(n log n)), by the Joret–Micek–Reed–Smid clique-coloring bound and Kim's triangle-free graphs, under the site's PROVED (LEAN) label.
Asks whether cliques of linear size force a sublinear clique transversal and which clique size k_c(n) forces a transversal below (1 − c)n; open, with k_c(n) ≥ n^{c'/log log n} (infinitely many n) and τ ≤ n − √(kn) from 1992.
Records the two-part Erdős–Pach–Pollack–Tuza diameter bound for connected graphs with no K_{2r} or K_{2r+1}: part (i) refuted in a refereed paper; part (ii) proved at r = 1, with pending claims that refute it.
Asks whether every graph with one edge fewer than a conjectured size Ramsey number splits into a bipartite graph and a graph of maximum degree below n; disproved for every n at least five by Pikhurko's constructions.
Determines the fewest edges of a graph on n vertices in which every set of k plus two vertices induces a subgraph of maximum degree at least k.
Asks whether a fixed saving below an eighth of n squared edges forces a graph on n vertices to contain a four-vertex clique or an independent set of n over log n vertices; disproved by Fox, Loh and Zhao.
Asks for the best bound t on the covering number of an r-uniform hypergraph, r at least three, in which every subhypergraph on at most 3r - 3 vertices has covering number at most one.
Asks whether r-coloring the edges of a complete graph on r squared plus one vertices forces r plus one vertices whose induced edges miss a color.
Records Alon's subquadratic triangle-free diameter-two completion theorem, the catalog's notation and diameter qualifications, and the earlier bounded-degree results.
Asks whether every connected triangle-free graph can be augmented to diameter at most four, still triangle-free, using fewer than (1-c)n edges.
Asks how large a triangle-free induced subgraph every K_4-free graph on n vertices must contain; the Erdős–Rogers problem, known to within a logarithmic factor in the refereed record and claimed to be sqrt(n log n) by a 2026 preprint.
Compares the largest set of edges meeting each triangle at most once with the fewest edges meeting every triangle, in a graph on n vertices.
Every regular graph of degree n plus one on two n vertices has a positive proportion of cyclic vertex subsets; the limiting constant is one half.
Asks whether a function on the finite subsets of a set of size aleph_omega that never picks a member of its input (a set mapping) must have an infinite independent set.
Asks to prove that H(n) minus the base-two logarithm of n tends to infinity, where H(n) is the least size such that some map from the subsets of an n-element set X to X sends the subsets of each set that large onto X.
Compares the cochromatic number, the fewest colors whose classes each induce a complete or empty graph, with the ordinary chromatic number.