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

About 55 years old · traced to 1971

Call a planar graph on $v$ vertices saturated if it has $3v-6$ edges. Must every graph on $n$ vertices with $⌊n^2/4⌋+⌊(n+1)/2⌋$ edges contain a saturated planar subgraph on more than three vertices?

References

Primary 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.

Additional 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.

graph-theory planar-graphs

InErdős Problems

Posted 1 month ago

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.

No solutions have been posted yet.