Let M be the class of finite maximal planar graphs. For G∈M, an edge card is a graph of the form G-e, where e∈ E(G). Define operatornameern_M(G) to be the least integer k for which there exist edges e_1,…,e_k∈ E(G) such that the cards G-e_1,…,G-e_k determine G up to isomorphism among graphs in M. Determine the universal class edge-reconstruction number max_G∈Moperatornameern_M(G). The cited preprint claims that this maximum is 2, that the octahedral graph has reconstruction number 2, and that some maximal planar graphs have reconstruction number 1.

Class edge-reconstruction number of maximal planar graphs

Let $\mathcal{M}$ be the class of finite maximal planar graphs. For $G\in\mathcal{M}$ , an edge card is a graph of the form $G-e$ , where $e\in E(G)$ . Define $\operatorname{ern}_{\mathcal{M}}(G)$ to be the least integer $k$ for which there exist edges $e_1,\ldots,e_k\in E(G)$ such that the cards $G-e_1,\ldots,G-e_k$ determine $G$ up to isomorphism among graphs in $\mathcal{M}$ . Determine the universal class edge-reconstruction number $\max_{G\in\mathcal{M}}\operatorname{ern}_{\mathcal{M}}(G)$ . The cited preprint claims that this maximum is $2$ , that the octahedral graph has reconstruction number $2$ , and that some maximal planar graphs have reconstruction number $1$ .

References

Primary source

arXiv

Additional references

The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two — arXiv

graph-reconstruction graph-theory

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new unrefereed preprint claims that two edge-removal clues always determine a maximal planar graph, and that some graphs genuinely need both.

The problem, posed in a 2010 survey, asks for the smallest universal number of edge-deletion cards needed to reconstruct every maximal planar graph. The new preprint claims the sharp answer is two, with some graphs requiring two cards and others reconstructible from one.

September 2, 2026 preprint

The preprint proves that two selected edge-deletion cards suffice for every maximal planar graph and gives examples requiring two. It characterizes the one-card cases only at the level stated in its abstract, so the claimed resolution is not independently verified.

Current status (as of September 2026): The universal upper bound of two and its sharpness are claimed in an unrefereed preprint; the precise one-card characterization and the complete proof remain unverified.

Sources

No solutions have been posted yet.