Status
On this page
Status
Topics
Status
On this page
Status
Topics
A planar graph on vertices with edges (the maximum possible) is called saturated. Does every graph on vertices with edges contain a saturated planar graph with vertices?
Source: erdosproblems.com/1019
An accepted solution exists. The statement is true.
Proved, in the site's label, which this page keeps with the qualification below. The site credits Simonovits's PhD thesis with the affirmative answer, in the stronger form that the graph contains a or a for some , and points to the comments for the proof, which it attributes to Cambie. The status-defining text is Simonovits's PhD thesis (Chapter 9, per the thread), unpublished and not held. The evidence in hand is of three kinds: Erdős's printed attestation of 1971, "Simonovits has just proved this conjecture [15], [34]" ([Er71], p. 102; the two references are Erdős's own 1969 and 1964 papers, not a text of Simonovits); the site's acceptance of a proof posted in the discussion thread on 21 November 2025 by the account StijnC after correspondence with Simonovits, which the site credits to Cambie (the community database's file history changes the problem to proved in a commit of that day); and Erdős's own partial result, Satz 1 of the 1969 paper (a saturated planar subgraph on more than vertices for edges), whose unspecified constant does not reach at the threshold. The forum proof is recorded below with its provenance and is not reproduced as this page's own; no refereed text of the theorem was found. Two third-party Lean developments state and prove the theorem (recorded under Formalization); neither was built or audited here, so they are formal support and not acceptance evidence. The label rests on a printed attestation of an unpublished thesis together with a site-accepted forum proof. The claim page Simonovits records the result as accepted on that documented evidence, with the same qualification, and the standing derives from it.