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, for each and all sufficiently large , every graph with edges and no isolated vertices has .
Asks for a bipartite graph with for each rational . The 2026 proof is accepted on a Lean development built here, and the page records the qualifications on its exposition.
Asks whether, for every , the most edges of a graph on vertices with no cycle of length or is ; disproved at and .
Asks whether every finite family with a bipartite member has a bipartite member with . It is false as written for two forests, and false for families of bipartite graphs with cycles by OpenAI's 2026 report.
Asks whether every graph on vertices with minimum degree at least contains vertex-disjoint -cycles (the Erdős–Faudree conjecture). Wang proved it in 2010 as Theorem B of a refereed paper.
Asks whether a random graph on vertices, with each edge included with probability , almost surely contains the -dimensional hypercube . Riordan proved it for every fixed edge probability above .
Asks whether, for fixed and large , every -free graph on vertices with at least edges has an independent set of size . It is false at by a Lean construction that Conjectures.io certified.
Asks for , the largest number of edges of a bipartite subgraph that every triangle-free graph with edges must contain. Alon determined its order, , with the exponent sharp; the exact value is open.
Asks whether some -free graph has a monochromatic triangle in every 2-coloring of its edges.
Asks whether there is a system of congruences covering all integers in which no modulus divides another.
Asks for the size of the largest subset of in which no non-empty subset has a square sum.
Asks whether every red/blue coloring of the edges of contains a red or a blue .
Asks whether every red-blue coloring of the pairs from the ordinal gives a red complete subgraph of that order type or a blue triangle.
Asks whether every graph with chromatic number at least contains all sufficiently large odd cycles.
Asks whether, for disjoint independent sets and in a graph, there are disjoint paths between them and a set that has exactly one vertex on each of these paths and meets every path from to .
Asks for the least number of colors that always suffices to color the union of countably infinite sets, any two meeting in other than points, with no set monochromatic.
Asks whether points on a sphere can have at least pairs at the same distance, for some .
Asks which values can occur as the number of distinct lines determined by distinct points in the plane. The values are determined for all sufficiently large , while the small cases are open.
Asks whether the number of distinct sets of line sizes determined by points in the plane is at most .
Asks whether every graph on vertices with more than edges has at least edges that lie in a .
Asks for estimates of the clique transversal number of an -vertex graph. Proved under erdosproblems.com's PROVED (LEAN) label, with the answer : the Joret–Micek–Reed–Smid clique-coloring bound gives the upper bound and Kim's triangle-free graphs the lower bound.
Asks whether every graph with one edge fewer than a conjectured size Ramsey number is the union of a bipartite graph and a graph of maximum degree below . Disproved for every by Pikhurko's constructions.
Asks whether, for some constant , every graph on vertices with at least edges contains a or an independent set of vertices. Disproved by Fox, Loh and Zhao.
Asks whether every triangle-free graph with maximum degree can be given diameter , still triangle-free, by adding edges; proved by Alon. The page also records the erdosproblems.com notation and diameter qualifications and the earlier bounded-degree results.
Asks whether there is a constant such that every connected triangle-free graph on vertices can be given diameter at most , still triangle-free, by adding fewer than edges.