Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphs

Background: The Kelly-Ulam reconstruction conjecture proposes that a graph's isomorphism class is determined by the classes of its multiset of vertex-deleted subgraphs. Although the conjecture has been verified for many families of undirected graphs, several cases remain unresolved. This analysis proposes a unified proof of the reconstruction conjecture for all finite undirected graphs. Methodology: A vertex-substitution framework is introduced, in which vertex-deleted subgraphs are augmented by a substitute vertex connected universally with characteristic edge weight (an arbitrary constant outside the deck alphabet). Vertex-substituted subgraphs have as many vertices as the parent graph, permitting tensor representation of the deck reconstruction.Results: Hypomorphism under vertex-deletion is shown to imply hypomorphism under vertex-substitution and vice-versa. In the vertex-substitution framework, bijections mapping cards be-tween hypomorphic decks are shown to map vertices between the parent graphs, demonstrating that an isomorphic mapping always exists. Conclusions: The Kelly-Ulam reconstruction conjecture is verified for finite, undirected graphs on at least three vertices. The vertex-substitution framework provides a unified analytical approach to the reconstruction conjecture for all undirected graphs.

Automated summary

This paper provides a unified proof method for the reconstruction conjecture of undirected graphs and verifies that the conjecture holds true for finite undirected graphs with at least three vertices.