Extremal and Structural Graph Theory

../

E0022/: Asks whether some graph on n vertices has at least n squared over 8 edges, no complete subgraph on 4 vertices, and no large independent set.

E0023/: Asks whether every triangle-free graph on 5n vertices can be made bipartite by deleting at most n squared edges.

E0024/: Asks whether every triangle-free graph on 5n vertices contains at most n to the fifth power many 5-cycles.

E0059/: Asks whether the number of graphs on n vertices containing no copy of a fixed graph is at most two raised to nearly the extremal number of edges.

E0060/: Asks whether every graph on n vertices with more edges than the extremal number for four-cycles contains at least about the square root of n four-cycles.

E0061/: Asks whether every graph on n vertices with no induced copy of a fixed graph has a clique or an independent set of size at least a fixed power of n.

E0062/: Asks whether two graphs of chromatic number aleph-one must share a common subgraph of chromatic number four, or even of countably infinite chromatic number.

E0064/: Asks whether every finite graph with minimum degree at least three contains a cycle whose length is a power of two with exponent at least two.

E0065/: Asks whether the reciprocals of the distinct cycle lengths of a graph with n vertices and kn edges sum to at least a constant times log k, and whether a complete bipartite graph minimizes that sum.

E0071/: Asks whether each infinite arithmetic progression with even numbers has a degree bound forcing every graph of that average degree to have such a cycle length.

E0072/: Asks whether some set of integers of density zero meets the cycle lengths of every large graph whose average degree is at least a fixed constant.

E0073/: Asks whether a graph whose every n-vertex subgraph has an independent set of at least (n-k)/2 vertices becomes bipartite after deleting a number of vertices bounded in terms of k.

E0081/: Asks whether the edges of any chordal graph on n vertices can be partitioned into about n squared over 6 cliques.

E0082/: Asks whether the largest regular induced subgraph guaranteed in every graph on n vertices has size growing faster than the logarithm of n.

E0084/: Asks whether the number f(n) of cycle sets of graphs on n vertices is o(2^n), and whether f(n)/2^(n/2) tends to infinity.

E0086/: Asks whether every subgraph of the n-dimensional hypercube with slightly more than half of its edges must contain a four-cycle.

E0113/: Asks whether a bipartite graph has Turan number O(n^(3/2)) exactly when it has no induced subgraph of minimum degree at least three.

E0127/: Asks whether the excess over a known bound in the number of edges of a largest bipartite subgraph of a graph with m edges is unbounded along some sequence of m.

E0128/: Asks whether a graph on n vertices whose every induced subgraph on at least half the vertices has more than n squared over fifty edges has a triangle.

E0133/: Determines the growth of the largest degree forced in every triangle-free graph on n vertices of diameter two, in particular whether it beats root n.

E0134/: Asks whether a triangle-free graph on n vertices with maximum degree below n to the power one half minus epsilon can reach diameter two by adding few edges.

E0136/: Determines the least number of edge colors of the complete graph on n vertices such that every four vertices span at least five colors.

E0146/: Asks whether a bipartite r-degenerate graph has extremal number at most n to the power two minus one over r; disproved at r equal to two by Theorem 1.2 of Chapter 10 of OpenAI's 2026 report, credited by the site's curator.

E0147/: Asks whether every bipartite graph of minimum degree r has extremal number at least order n to the power two minus one over r minus one, plus a positive gain.

E0149/: Asks whether the strong chromatic index of any graph, the least number of induced matchings partitioning its edges, is at most five quarters of the squared maximum degree; open, with the refereed record at 1.772 times it.

E0150/: Asks whether the n-th root of the maximum number of minimal disconnecting vertex sets of a graph on n vertices tends to a limit below two; proved, the limit lying between 1.4457 and the golden ratio by refereed papers.

E0151/: Asks whether every graph on n vertices has a clique transversal of at most n minus the triangle-free independence bound H(n) vertices (Erdős–Gallai); open; best bounds n − √(2n) + √2 (explicit) and n − c√(n log n) (asymptotic).

E0167/: Asks whether a graph with at most k edge-disjoint triangles can be made triangle-free by deleting at most 2k edges (Tuza's conjecture); open, the site's label falsifiable, with Haxell's 66/23 the best refereed constant.

E0180/: Asks whether every finite family of forbidden graphs contains one member whose own extremal edge count is comparable to that of the whole family.

E0182/: The maximum number of edges on n vertices with no k-regular subgraph, and whether it is barely more than linear in n, for every k at least 3.

E0184/: Asks whether every graph on n vertices decomposes into at most a constant times n edge-disjoint cycles and single edges, the Erdős-Gallai cycle decomposition conjecture; answered yes by the OpenAI release's 2026 theorem.

E0426/: Asks whether some graph on n vertices has as many as two to the number of vertex pairs divided by n factorial distinct subgraphs occurring in exactly one way.

E0500/: Asks for the largest number of triples on n vertices with no four vertices carrying all four of their triples, Turán's tetrahedron problem; the density lies between Turán's 5/9 and a flag-algebra bound of 0.5615.

E0533/: Asks whether a graph on n vertices with no complete subgraph on five vertices and a positive edge density has a triangle-free set of linearly many vertices.

E0548/: Records the proved Erdős–Sós tree edge bound and the precise relation between its sharp threshold and the site's statement.

E0571/: Every rational exponent in [1,2) is realized by the Turán number of a finite bipartite graph; records the 2026 proof, accepted on Lean built here, and its exposition qualifications.

E0572/: Asks whether, for every k at least three, some graph on n vertices with no cycle of length two k has at least a constant times n to the power one plus one over k edges; known for k equal to 3 and 5, open for every other k.

E0573/: Asks whether the most edges a graph on n vertices can have with no triangle and no four-cycle is asymptotic to n over two to the power three halves; the ratio is known only to lie between one and the square root of two.

E0574/: Asks whether the most edges on n vertices avoiding cycles of length two k minus one and two k is asymptotic to n over two to the power one plus one over k, for k above one; disproved at k equal to 3 and 5.

E0575/: Asks whether the extremal number of a finite family with a bipartite member is within a constant factor of some bipartite member's; false as written for two forests, and false for cyclic bipartite families by OpenAI's 2026 report.

E0576/: Determines how many edges a graph on n vertices can have without containing the k-dimensional hypercube graph; for the cube the order lies between n to the three halves and n to the eight fifths, refuting Erdős's first guess.

E0577/: Asks whether every graph on four k vertices with minimum degree at least two k contains k vertex-disjoint four-cycles; the Erdős-Faudree conjecture, proved by Wang in 2010 as Theorem B of a refereed paper.

E0578/: Asks whether a random graph on two to the d vertices with each edge included with probability one half almost surely contains a d-dimensional hypercube; proved by Riordan for every fixed edge probability above one quarter.

E0579/: Asks whether a large dense graph on n vertices with no complete tripartite subgraph having two vertices per class must have a linear independent set; false at edge density 3/2048 by a Lean construction Conjectures.io certified.

E0580/: Asks whether every graph on n vertices in which at least half the vertices have degree at least n over two contains every tree on at most n over two vertices; proved by Zhao for large n, with finitely many orders unchecked.

E0581/: Determines the largest number of edges of a bipartite subgraph that every triangle-free graph with m edges must contain; known to the order m/2 + Theta(m^{4/5}) by Alon, the exponent sharp and the exact value open.

E0583/: Asks whether every connected graph on n vertices can be split into at most n over two rounded up edge-disjoint paths; Gallai's path decomposition conjecture, proved for several classes and open in general.

E0584/: Asks whether every graph on n vertices with edge density delta, allowed to shrink as a power of n, contains dense subgraphs in which any two edges lie together on a short cycle.

E0585/: Asks for the most edges a graph on n vertices can have without two edge-disjoint cycles on exactly the same vertex set; known to lie between n log log n and n times a power of log n.

E0600/: Asks whether the least edge count forcing an edge in r triangles, when every edge lies in a triangle, has differences going to infinity and ratios going to one.

E0608/: 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.

E0610/: 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.

E0611/: 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.

E0612/: 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.

E0614/: 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.

E0616/: 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.

E0617/: 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.

E0618/: Records Alon's subquadratic triangle-free diameter-two completion theorem, the catalog's notation and diameter qualifications, and the earlier bounded-degree results.

E0619/: 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.

E0620/: 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.

E0621/: 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.

E0622/: 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.

E0641/: Asks whether a high enough chromatic number forces a graph to contain k edge-disjoint cycles on the same vertex set, for every k.

E0642/: Asks whether a graph on n vertices in which every cycle has more vertices than chords can have at most a constant times n edges.

E0666/: Asks whether every subgraph of the n-dimensional hypercube with a positive fraction of its edges contains a six-cycle, once n is large enough.

E0712/: Asks for the Turán density of the complete r-uniform hypergraph on k vertices for any k > r > 2; Turán's 1941 theorem settles r = 2 and no pair with r > 2 is known, with Erdős's two prize offers standing.

E0713/: Asks whether every bipartite graph with at least two edges has extremal number asymptotic to a constant times a power of n in [1, 2), and whether that power is rational; Erdős's 1967 exponent shapes were disproved in 1970.

E0714/: Asks whether the largest graph on n vertices with no complete bipartite subgraph with r vertices per side has roughly n to the power 2 minus one over r edges.

E0715/: Asks whether every 4-regular graph contains a 3-regular subgraph, and whether some degree r forces one in every r-regular graph; both answered yes by Tashkinov in 1982, for degree 4 and for every degree at least 3.

E0717/: Asks whether the chromatic number of an n-vertex graph is at most a constant times n^{1/2}/log n times the order of its largest clique subdivision; the Erdős–Fajtlowicz conjecture, proved by Fox, Lee and Sudakov in 2013.

E0718/: Asks whether a constant times r squared times n edges on n vertices always force a subdivision of the complete graph on r vertices; the conjecture of Erdős, Hajnal and Mader, proved by Bollobás–Thomason and Komlós–Szemerédi.

E0742/: Asks whether a graph on n vertices of diameter two in which deleting any edge raises the diameter has at most n squared over four edges; proved by Füredi for all large n, with one unreviewed proof claim for every n.

E0743/: Asks whether the complete graph on n vertices can always be split into edge-disjoint copies of given trees with 2, 3, up to n vertices; the tree packing conjecture of Gyárfás, open, with one arXiv proof claim withdrawn.

E0745/: Asks for the size of the second largest component of the random graph on n vertices with edge probability one over n; the site credits Komlós, Sulyok and Szemerédi's supercritical log n bound; Aldous (1997) gives n^(2/3).

E0746/: Asks whether the uniform random graph on n vertices with slightly more than half of n times log n edges is almost surely Hamiltonian; the Erdős-Rényi conjecture, settled by Korshunov and by Komlós and Szemerédi.

E0752/: Asks whether a graph with minimum degree k and no cycle of length at most twice s must have at least a constant times k to the power s distinct cycle lengths.

E0765/: Asks for an asymptotic formula for the largest number of edges of a graph on n vertices containing no cycle of length four.

E0766/: Asks for estimates of the least Turán number over all graphs with k vertices and l edges in the range k < l ≤ k²/4, and whether it is strictly monotone in l; open, with asymptotics known at the pairs (5,6) and (6,9) only.

E0767/: Asks whether the most edges on n vertices with no cycle carrying k chords at one cycle vertex is (k+1)n minus (k+1) squared for large n; proved for n at least 3k+3 by Jiang (2004), with a 2026 preprint claiming the threshold.

E0777/: Asks how many comparable pairs a family of m subsets of one to n can have for m near 2^(n/2); three questions answered yes, no, yes by Alon and Frankl and by Alon, Das, Glebov and Sudakov.

E0778/: Asks whether the first player can win the game of alternately coloring edges of a complete graph so that her largest monochromatic clique beats her opponent's.

E0794/: Asks whether every three-uniform hypergraph on 3n vertices with more than n cubed edges has four vertices spanning three edges; false as written by a 28-edge example, while the Turán density of K_4 minus an edge stays open.

E0802/: Asks whether every K_r-free graph on n vertices with average degree t has an independent set of order n log t over t; true for r = 3 since 1980, and for every r at least 4 by a Lean-checked theorem of the 2026 OpenAI release.

E0803/: Asks whether every graph with n log n edges has an almost-regular subgraph on m vertices with much more than m log m edges; false by Alon's 2008 random bipartite construction, with Janzer and Sudakov's bound the best positive one.

E0804/: Estimates the largest independent set forced in a graph on n vertices where every induced subgraph on m vertices has an independent set of size log n.

E0805/: Characterizes the functions g for which some graph on n vertices has every induced subgraph on g of n vertices with a clique and independent set of size log n.

E0807/: Asks whether the random graph with edge probability one half almost surely needs exactly n minus its independence number complete bipartite graphs to partition its edges; disproved by Alon, then by Alon, Bohman and Huang.

E0813/: Estimates the largest clique forced in an n-vertex graph where every seven vertices span a triangle: the exponent lies between 5/12 (Bucić and Sudakov) and 1/2 (Erdős and Hajnal), and whether either end can be moved is open.

E0814/: Asks whether a graph with one edge more than the count forcing a subgraph of minimum degree k has such an induced subgraph on a constant fraction fewer vertices; proved by Sauermann for k at least 3, with k = 2 elementary.

E0815/: Asks whether a graph with n vertices, 2n - 2 edges and no proper induced subgraph of minimum degree 3 has a cycle of each fixed length k for large n; false at k = 23 (Narins, Pokrovskiy, Szabó), true for k up to 6, even k open.

E0816/: Asks whether a graph with 2n + 1 vertices and n^2 + n + 1 edges has two equal-degree vertices joined by a path of length 3; corrected to n at least 2, since n = 1 (the triangle) fails; proved for n at least 600 by Chen and Ma and claimed for every n at least 2 by Liu and Zeng.

E0883/: Asks whether a subset of one to n above the triangle threshold of the coprime graph forces all odd cycles up to n/3 + 1 and, for large n, complete (1, l, l) tripartite subgraphs; the second was settled by Sárközy in 1999.

E0900/: Asks whether the uniform random graph with n vertices and cn edges, c above one half, almost surely has a path of length f(c)n with f tending to 0 at one half and to 1 at infinity; proved by Ajtai, Komlós and Szemerédi, 1981.

E0902/: Estimates the least order of a tournament in which every n vertices have a common dominator; open, with Erdős's 1963 upper bound and the Szekeres and Szekeres lower bound of 1965 a factor of order n apart, exact only to n = 3.

E0904/: Asks whether, for n at least r, a graph with n vertices and at least the Turán number of edges for r plus one has an r-clique of degree sum at least 2rm/n; proved by Bollobás and Nikiforov in 2005, while the site's wording, with no range, fails below r vertices.

E0905/: Asks whether every graph on n vertices with more than n^2/4 edges has an edge on at least n/6 triangles; proved by Khadzhiivanov and Nikiforov in 1979, by Edwards (unpublished) and by Bollobás and Nikiforov in 2005.

E0914/: Asks whether every graph on rm vertices with minimum degree at least m(r−1) has m vertex-disjoint copies of K_r; Erdős's conjecture, proved by Hajnal and Szemerédi in 1970 and reproved in refereed papers of 2008 and 2010.

E0915/: Asks whether a graph with 1+n(m−1) vertices and 1+n·C(m,2) edges has two vertices joined by m disjoint paths; false for m at least 5 if the paths are vertex-disjoint, true for every m if edge-disjoint; the site labels it solved.

E0916/: Asks whether, for n at least 4, every graph with n vertices and 2n−2 edges has a cycle and a further vertex adjacent to three of its vertices; proved by Thomassen in 1974, while the site's wording, with no range, fails at n = 1.

E0926/: Bounds by n to the power three halves the edges of an n-vertex graph avoiding a fixed graph made of a vertex joined to k others whose pairs are linked.

E0927/: Asks whether the largest number of distinct clique sizes in a graph on n vertices is n minus log_2 n minus the iterated-logarithm count, up to O(1); disproved by Spencer, whose construction removes the iterated term.

E0934/: The least number of edges forcing a graph of maximum degree at most d to have two edges at distance at least t; open, exact for t = 1, t = 2 and h_3(3) = 23, between 0.629^t d^t and 3d^t/2 + 1 in general, with 2026 preprints at t = 3.

E0993/: Asks whether the sequence counting the independent sets of each size in a tree or forest is unimodal.

E1006/: 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.

E1007/: 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.

E1008/: 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.

E1009/: 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.

E1010/: 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.

E1011/: 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.

E1012/: 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.

E1016/: 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.

E1017/: 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.

E1018/: 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.

E1019/: 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.

E1021/: 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.

E1031/: Asks whether a graph on n vertices with no empty or complete subgraph of size ten times the logarithm of n has an induced non-trivial (neither empty nor complete) regular subgraph of logarithmic size.

E1033/: Estimates the largest degree sum forced on a triangle in a graph on n vertices with more than n²/4 edges, and asks whether it is at least about 1.464 n; open, between Fan's 21n/16 and a construction's 2(√3 − 1)n + O(1).

E1034/: Asks whether a graph on n vertices with more than n²/4 edges has a triangle to which nearly half of all vertices are joined twice; the Erdős–Faudree conjecture, disproved by Ma and Tang's construction with constant 2 − √(5/2).

E1035/: Asks whether some positive c makes minimum degree above one minus c times two to the n force an n-dimensional hypercube in a graph on two to the n vertices.

E1036/: Asks whether a graph on n vertices with no empty or complete subgraph of logarithmic size has exponentially many pairwise non-isomorphic induced subgraphs.

E1037/: Asks whether a graph on n vertices with each degree repeated at most twice and more than half of n distinct degrees has a large empty or complete subgraph.

E1066/: Concerns the graph on n plane points that are pairwise at least distance one apart, with edges joining the pairs exactly distance one apart.

E1077/: Asks whether every graph with n^{1+α} edges has an almost-regular subgraph on more than n^{1−α} vertices with εm^{1+α} edges; false as written, with n^α the right size on the site's account of a 2025 preprint.

E1078/: Asks whether an r-partite graph with n vertices per part and minimum degree about (r − 3/2)n must contain a complete graph on r vertices; proved by Haxell, with the exact threshold from Haxell and Szabó by complementation.

E1079/: Asks whether a graph with the Turán number of edges has a linear-degree vertex whose neighborhood has the Turán number of edges for r − 1; proved by Bollobás and Thomason in 1981, strengthened by Bondy in 1983.

E1080/: Asks whether a bipartite graph on n vertices with a part of size about n^(2/3) and at least cn edges must contain a six-cycle; disproved by the superlinear 6-cycle-free constructions credited by the site, papers not held.

E1111/: Asks whether bounded clique number and large chromatic number force two anticomplete vertex sets both of large chromatic number; the El-Zahar-Erdős problem, open beyond the case of chromatic number three.

E1155/: Asks for the typical structure of the graph left by repeated uniform random triangle removal from K_n and whether its edge count has order n^{3/2}; the sharp constant is formally verified, and the typical structure is open.

E1157/: Asks for the most edges an r-graph on n vertices can have with no k vertices spanning s edges, the Brown-Erdős-Sós problem; the conjecture's s = 3 case and large-uniformity linear form are proved; 3-graphs with k = s + 3, s ≥ 4, open.

E1158/: Asks whether Erdős's 1964 upper exponent for the Turán number of the complete t-partite t-uniform hypergraph with r vertices per class is attained up to o(1); known only for t = 2 and r at most 3.

---

Turan-type extremal problems for graphs and hypergraphs, forbidden subgraphs and edge counts, cycles and girth, degree and subgraph-counting conditions, planarity, and structural questions such as the Erdos-Hajnal conjecture.

Site tags routed here: combinatorics, cycles, graph theory, hypergraphs, number theory, planar graphs, turan number.