Erdős Problem #1019 — Forcing a nontrivial saturated planar subgraph
For an integer , let be a simple graph with vertices and exactly
edges. A planar graph on vertices is called saturated here if it has the maximum possible number of edges. Must every such contain a subgraph (not necessarily an induced subgraph) with that is planar and satisfies
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 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 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 vertices and edges contains a saturated planar subgraph on vertices. That bound addresses the size obtainable as the excess grows; the present threshold instead asks whether an excess of about 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.
Progress summary
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.