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 for the largest number of vertices that a two-colored complete graph can force to be left over when it is covered by disjoint monochromatic copies of . Burr, Erdős and Spencer determined it for fixed and large in terms of , so it grows exponentially.
Asks to estimate the number of edge-disjoint complete graphs needed to partition the edges of a graph on vertices with more than edges. Plasma AI's Lean-checked formula , uniform in , answers it to within .
Asks whether, for large , every graph on vertices with at least edges has a non-planar subgraph of bounded size. Answered yes by Kostochka and Pyber in 1988, through a subdivided of bounded size.
Asks whether every graph on vertices with edges contains a saturated planar subgraph on more than vertices. Proved by Simonovits in a PhD thesis, as attested by Erdős and erdosproblems.com.
Asks whether, for every , for some , where is the bipartite graph joining each pair among vertices to its own vertex.
Asks whether a family of sets of size at least , with few members 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 in which no member is a union of others has size for some constant .
Asks to estimate how large an independent set every -uniform hypergraph on vertices must have when any two edges share at most one vertex.
Asks to estimate how large an independent set must exist for every map sending each pair from to a third element, where is independent if for all .
Asks how large, relative to , the largest sum of a monotonic subsequence of a sequence of distinct real numbers must be.
Asks whether, for a family of at most sets of size with union and large, there are sets that meet every member of but contain none.
Asks for an estimate of , the least possible maximum over of for a function with values .
Asks whether a graph on vertices with no empty or complete subgraph on vertices has an induced regular subgraph on vertices that is neither empty nor complete.
Asks whether every graph on vertices with more than edges has a triangle with more than vertices each joined to at least two of its vertices. This is the Erdős–Faudree conjecture, disproved by Ma and Tang's construction with constant .
Asks whether a graph on vertices with no empty or complete subgraph on more than vertices has pairwise non-isomorphic induced subgraphs.
Asks whether a graph on vertices with each degree occurring at most twice and more than distinct degrees has an empty or complete subgraph much larger than .
Asks whether can have components for monic of degree with roots in a closed of transfinite diameter in no closed disc of radius , and whether it has at most , with , when the diameter is below .
Asks whether every monic non-constant polynomial has a line onto which projects to a set of measure at most .
Asks for the infimum of , the largest boundary length of a connected component of , over polynomials with every .
Asks whether, for a monic polynomial , the set lies in a disc of radius whenever it is connected.
Asks whether, for a monic polynomial with distinct roots and small enough that has connected components, all these components must be convex.
Asks whether, for a monic polynomial with all roots in for some , the set must have a connected component of diameter .
Asks whether is irrational for every increasing integer sequence with .
Asks whether the number of Carmichael numbers up to satisfies . The answer is yes, by a Lean proof submitted to a bounty site in October 2026 and replayed in the kernel here.