Source-linked AI summary
The Class Edge-Reconstruction Number of a Maximal Planar Graph Is One or Two
Sergey Ivanov
TL;DR
The paper asks how many selected edge cards identify a maximal planar graph when its class is known, a question not settled by complete edge-deck results. Using the two-parent structure of flippable-edge cards together with degree-based arguments, it proves that at most two cards always suffice and that this bound is sharp, while one-card cases remain characterized only card-theoretically.
Problem
Complete edge-deck reconstruction results do not determine how many selected cards suffice within maximal planar graphs.
Method
The proof uses flippable-edge cards with at most two maximal-planar parents, then applies degree signatures and a degree-transfer identity to exclude the rival.
Results
At most two selected edge cards identify every finite simple maximal planar graph, and the octahedral graph has class edge-reconstruction number two.
Takeaways & Limitations
The sharp universal bound is two, while some graphs are identifiable by one card and an exact card-based one-card test is available.
Takeaways & Limitations
The paper resolves the numerical question but does not provide an intrinsic structural classification of all maximal planar graphs for which one card suffices.
Abstract
from arXiv · showhide
An edge card of a graph is obtained by deleting one edge, and a class edge-reconstruction number asks for the fewest carefully selected cards that identify the graph when its class is known. We determine the sharp universal bound for maximal planar graphs. Two selected cards always suffice, and the octahedral graph shows that two can be necessary; some maximal planar graphs are already identified by one card. The argument exploits the fact that deleting a flippable edge leaves a single quadrilateral whose two diagonals give the only possible maximal-planar completions. Degree information then rules out the competing completion, with a separate argument for graphs containing a vertex of degree three. This settles a problem posed in a 2010 survey on reconstruction numbers.
1 Introduction
The paper addresses the selected-card reconstruction problem for maximal planar graphs, extending prior full-deck and vertex-card results. It proves that two cards always suffice, correcting an ancillary survey claim while leaving the central problem intact.
- 1 Introduction: 3n −6 edge cards comprise the complete edge deck, but the paper asks whether far fewer selected cards suffice within maximal planar graphs.Earlier full-deck edge-reconstruction theorems do not answer this selected-card question.
- 1 Introduction: The 2010 survey explicitly posed the question of the class edge-reconstruction number of a maximal planar graph.
- 1 Introduction: Two selected edge cards always suffice, and two is the sharp universal bound.
- 1 Introduction: The proof reduces a flippable-edge card to at most two maximal-planar candidates, then uses degree signatures or a degree-transfer identity to exclude the rival.
- 1 Introduction: The paper corrects the survey’s claim that no maximal planar graph has class edge-reconstruction number one; the unique five-vertex triangulation and infinitely many further examples contradict it.
2 Selected edge cards and the main result
This section formalizes selected edge-card reconstruction within the class of maximal planar graphs and states the main bound. It also gives an exact one-card test, while noting that the test is not an intrinsic classification.
- 2 Selected edge cards and the main result: An edge card G −e retains both endpoints after deleting one edge, and the edge deck is the multiset of unlabeled edge-card isomorphism types.
- 2 Selected edge cards and the main result: A selected subdeck identifies G when every maximal-planar graph containing it is isomorphic to G; the reconstruction number counts selected cards with multiplicity.
- 2 Selected edge cards and the main result: Two selected cards may be distinct physical copies of one isomorphism type, but cannot exceed that type’s deck multiplicity.
- 2 Selected edge cards and the main result: Every finite simple maximal planar graph is identifiable from at most two selected edge cards, and some graphs require two.
- 2 Selected edge cards and the main result: A maximal-planar parent of a card X is a graph H whose deletion of some edge produces a graph isomorphic to X.
- 2 Selected edge cards and the main result: A graph has class edge-reconstruction number one exactly when one edge card has no nonisomorphic maximal-planar parent.This is an exact card-based test, not an intrinsic structural classification of all one-card triangulations.
3 The local diagonal picture
Deleting a flippable edge creates one quadrilateral whose two diagonals determine the only maximal-planar parents of the resulting card. Reconstruction therefore becomes a two-candidate problem.
- 3 The local diagonal picture: An edge uv is flippable when the third vertices x and y of its incident facial triangles are nonadjacent.
- 3 The local diagonal picture: Deleting a flippable edge merges its incident triangles into a single quadrilateral.
- 3 The local diagonal picture: The resulting card is three-connected, so its spherical embedding is unique.
- 3 The local diagonal picture: The original diagonal and the flipped diagonal are the only maximal-planar parents of the card, up to isomorphism.
- 3 The local diagonal picture: If the two parents are nonisomorphic, a second card must be chosen that the flip mate lacks, possibly by exploiting card multiplicity.
4 Road map of the proof
The proof splits by minimum degree: degree-four or degree-five vertices provide multiple flippable edges, while cubic vertices require a degree-transfer argument. In both cases, carefully chosen cards eliminate the competing maximal-planar completion.
- Every maximal planar graph has minimum degree at least three and a vertex of degree at most five, yielding the proof’s two cases.
- Minimum degree at least four: A degree-four vertex has at least two flippable incident edges, while a degree-five vertex has at least three.Noncrossing blocker chords limit blocked spokes around the minimum-degree vertex.
- Minimum degree at least four: After a suitable flip, degree changes at the old and new diagonal endpoints guide a second deletion whose low-degree signature excludes the flip mate.In regular cases, multiplicity can distinguish isomorphic selected cards.
- Minimum degree at least four: A maximal planar graph of minimum degree at least four is identified by at most two selected edge cards.
- The cubic case: The cubic case uses a degree-transfer identity and analyzes the three edges surrounding a degree-three vertex to obtain the same two-card bound.The residual possibilities are reduced to regularity, bipartiteness, the five-vertex triangulation, or an impossible neighborhood.
5 Sharpness and one-card reconstruction
Small and infinite families demonstrate one-card reconstruction, while the octahedron establishes that two cards are sometimes necessary. The distinction arises from whether competing completions are isomorphic or differ in card multiplicity.
- The smallest transparent one-card example: The unique maximal planar graph on five vertices, K5 −e, has class edge-reconstruction number one.Any edge card retains five vertices, so its maximal-planar parent is forced by uniqueness.
- The infinite one-card family: For every m ≥4, the graph Jm in the bipyramid family has class edge-reconstruction number one.Its relevant card has a degree-two vertex whose two maximal-planar completions are isomorphic under swapping the hubs.
- Why the bound two is sharp: The octahedral graph is four-regular and edge-transitive, so deleting any edge produces the same card type.
- Why the bound two is sharp: The octahedral graph has class edge-reconstruction number two.Its flip mate contains only one copy of the common card, whereas two copies identify the octahedron.
- One-card graphs can have isomorphic competing completions, whereas two-card graphs may require multiplicity to distinguish nonisomorphic completions.
6 Concluding remarks
The numerical theorem is settled, but the intrinsic structure of one-card graphs remains open. The proof also separates selected-card reconstruction from full-deck reconstructibility and suggests broader surface-triangulation questions.
- An open problem is to characterize intrinsically the maximal planar graphs for which one card suffices.The exact criterion is currently expressed through the parents of a card, and infinitely many one-card examples exist.
- Full-deck reconstructibility and reconstruction numbers should be treated separately because the two-card theorem controls one local ambiguity with a short certificate.Analogous ideas for other surfaces would require additional care with embedding uniqueness and global topology.
A Planar preliminaries and small graphs
Maximal planar graphs have triangular spherical embeddings, constrained degree structure, and rigid local neighborhoods. These facts establish the preliminaries used to analyze edge deletions and small exceptional orders.
- For n ≥3, maximal planar graphs have triangular faces and |E| = 3n −6; for n ≥4, they are three-connected.
- Euler’s formula gives a vertex of degree at most five, while every maximal planar graph has minimum degree at least three.The neighbors of a vertex occur cyclically on its link.
- Two adjacent degree-three vertices force the entire graph to be K4.Their neighborhoods and facial triangles form the complete spherical embedding of K4.
- Except in K4, degree-three vertices are independent, and deleting a cubic vertex leaves a maximal planar graph.Its three neighbors bound the face created by the deletion.
- Small graphs: The maximal planar graphs on three, four, and five vertices are uniquely K3, K4, and K5 −e, respectively, and each has class edge-reconstruction number one.An edge card fixes the order, so uniqueness forces its maximal-planar parent.
- Deleting an edge from two maximal-planar parents leaves a three-connected graph with one quadrilateral face, whose two diagonals are the only possible completions.This establishes the local two-candidate structure underlying the reconstruction argument.
C Degree bookkeeping
Degree-sequence bookkeeping tracks how deleting an edge changes endpoint degrees, constraining when two maximal-planar completions could share matching edge-card signatures.
- Degree deletion identities: The deletion identity records the degree-sequence change caused by removing an edge through the endpoint-degree vector and the linear map L.The map L is injective on finite-support integer vectors, making these degree changes recoverable.
- Residual comparison: Matching edge-card degree sequences between two completions yields a residual vector whose positive and negative parts have common mass r ∈ {0, 1, 2}.The comparison is applied to cards from both completions and their common card.
- Residual cases: If r = 2, every edge has the same unordered endpoint-degree pair; if r = 1, one fixed degree class forms a vertex cover.These alternatives sharply restrict the structure of a graph whose cards all admit degree-sequence matches in the rival completion.
D Graphs of minimum degree at least four
For maximal planar graphs with minimum degree at least four, flippable edges near low-degree vertices provide degree signatures that distinguish a graph from its flip mate.
- Flippable edges: A degree-four vertex is incident with at least two flippable edges, while a degree-five vertex is incident with at least three.Nonflippable spokes require pairwise noncrossing blocker chords in a quadrilateral or pentagon.
- Low-degree structure: When the vertices above minimum degree form a nonempty independent set, a flippable edge with both endpoints at minimum degree exists.Otherwise, noncrossing constraints around a minimum-degree vertex contradict the assumed absence of such an edge.
- Degree signatures: After flipping an edge, its old endpoints lose one degree and the new endpoints gain one, creating distinctive low-degree card signatures.The proof selects a second deletion whose signature cannot occur among the flip mate’s cards.
- Reconstruction: Two selected cards exclude the flip mate either through an absent degree signature or, in the regular case, through card multiplicity.The two-parent lemma then identifies the original maximal planar graph.
E Graphs with a cubic vertex
Graphs with a cubic vertex require a separate contradiction argument: the neighbors of the cubic vertex generate flippable boundary edges, and degree bookkeeping eliminates every possible rival completion.
- Cubic configuration: After excluding small graphs, the three boundary edges around a cubic vertex are all flippable, producing competing completions for each boundary card.Each opposite face vertex lies outside the cubic vertex’s neighborhood, so the corresponding flip is available.
- Degree constraints: Degree-sequence comparisons force one fixed degree class to meet every edge, while residual mass two is impossible for the boundary-edge comparisons.Mass two would imply a fixed endpoint-degree pair on every edge, leading to bipartiteness or regularity contradictions.
- Final contradiction: For p ≥ 6, the required degree-three–degree-four edge cannot exist in the flip mate, yielding the final contradiction.Unchanged cubic vertices have neighbors of degree at least five, while the new degree-four vertex has neighbors of degrees p−1, p−1, p, p.
F Sharpness, examples, and assembly
The sharp class edge-reconstruction number for maximal planar graphs is two: the octahedron requires two cards, while other examples require only one. Exhaustive computation independently corroborates that no graph exceeds this bound.
- One-card examples: One card identifies a maximal planar graph exactly when the card has no nonisomorphic maximal-planar parent besides the graph itself.This criterion also characterizes the one-card case through maximal-planar parents of the card.
- One-card examples: The order-five graph K5 −e is uniquely maximal planar, so it requires one card.Every maximal-planar parent of a five-vertex card has five vertices, and K5 −e is the unique graph of that order.
- The sharp example: The octahedron requires two cards because one card has two possible parents, whereas two copies of the card exclude its nonisomorphic flip mate.The octahedron is edge-transitive; its cards have degree sequence 32, 44, while the flip mate contains exactly one such card.
- Assembly of the sharp bound: Both reconstruction numbers occur: the octahedron has value two, while K5 −e and the graphs Jm have value one.Together with the universal upper bound, these examples establish that the class-wide maximum is exactly two.
- Independent audit: A computer-free proof is independently checked by exhaustive generation and canonical testing of one- and two-card submultisets through thirteen vertices.The audit tested every maximal-planar parent and retained card multiplicities; its computations are corroborative rather than part of the proof.
- Independent audit: The audit found no maximal planar graph with class edge-reconstruction number above two.Table 1 partitions all unlabeled maximal planar graphs by order according to whether their reconstruction number is one or two.