← All problems

Erdős Problem #1019 — Forcing a nontrivial saturated planar subgraph

55 years old · traced to

For an integer n≥4n\ge 4, let GG be a simple graph with nn vertices and exactly

m(n)=⌊n24⌋+⌊n+12⌋m(n)=\left\lfloor\frac{n^2}{4}\right\rfloor+\left\lfloor\frac{n+1}{2}\right\rfloor

edges. A planar graph HH on v(H)≥3v(H)\ge 3 vertices is called saturated here if it has the maximum possible number 3v(H)−63v(H)-6 of edges. Must every such GG contain a subgraph HH (not necessarily an induced subgraph) with v(H)>3v(H)>3 that is planar and satisfies

e(H)=3v(H)−6?e(H)=3v(H)-6?

Erdős Problems #1019 Erdős (1971)

Background

The edge threshold sits just above the Turán threshold for forcing a triangle: every graph with ⌊n2/4⌋+1\lfloor n^2/4\rfloor+1 edges contains one, and a triangle is itself a saturated planar graph. The question asks whether the additional edges force a larger maximal planar subgraph. Erdős also described a construction with ⌊n2/4⌋+⌊(n−1)/2⌋\lfloor n^2/4\rfloor+\lfloor(n-1)/2\rfloor edges and no saturated planar subgraph on more than three vertices. This is exactly one edge below the questioned threshold, making the proposed bound sharp if the assertion holds. Erdős Problems #1019 Erdős (1971)

The problem belongs to Erdős’s work on saturated planar subgraphs, with related references dating to 1964 and 1969. In 1969, Erdős proved a more quantitative result: a graph with nn vertices and ⌊n2/4⌋+k\lfloor n^2/4\rfloor+k edges contains a saturated planar subgraph on ≫k/n\gg k/n vertices. That bound addresses the size obtainable as the excess kk grows; the present threshold instead asks whether an excess of about n/2n/2 forces even a subgraph on just four or more vertices. Erdős (1964) Erdős (1969) Erdős Problems #1019

References

P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.

Source: P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press (1971), 97–109.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.