Graph reconstruction conjecture

Draw four dots in a chain, with three lines joining consecutive dots. Delete one dot and its incident lines at a time. Deleting either end leaves a three-dot chain; deleting either middle dot leaves one line and an isolated dot. Keep all four little drawings, including repeats, but remove names. Would this collection of partial views always determine the original network up to renaming?[1]

Suppose every one-vertex deletion of a finite graph is available, but vertex names are absent from each resulting card. Is the original connection pattern uniquely determined? A deck is a multiset: a collection retaining the number of times each shape occurs. In a four-vertex path, two cards are three-vertex paths and two are one edge plus an isolated vertex.

The conjecture concerns simple undirected graphs, with no loops or repeated edges, on $n\geq3$ vertices. If $\mathcal D(G)=\mathcal D(H)$, must there be a vertex renaming preserving every edge and nonedge between $G$ and $H$? Graphs related by such a renaming are called isomorphic. Labels used to describe an example are not extra information supplied with its cards.[1] [2]

The conjecture covers finite networks with at least three dots, undirected lines, no loops and no multiple lines between a pair. It asks for every such network. Working examples and recoverable statistics do not yet prove that two different networks can never share the same collection.[1]

Some information is already recoverable. Each original edge appears in exactly $n-2$ cards, since deleting either endpoint removes it. Hence

$$|E(G)|=\frac{\sum_{C\in\mathcal D(G)}|E(C)|}{n-2},$$

counting every repeated card. In the path example the card edge counts are $2,2,1,1$, giving $6/2=3$ original edges. Subtracting each card's count from three recovers the deleted vertices' degrees: $1,1,2,2$.

These totals do not specify every connection. For instance, a five-vertex path and a separate triangle plus an edge both have degrees $1,1,2,2,2$, yet are different graphs. They do not have the same full deck. The general deck-uniqueness statement remains the gap.[1] [2]

Missing names make the information question sharp: there is no given way to match a dot in one view to a dot in another. The interest is whether their overlap nevertheless preserves every connection, rather than merely totals or summaries.[1]

A full answer would identify whether the cards lose any structural information once names are removed. With only two vertices, a joined pair and an unjoined pair both leave two single-dot cards; this explains the lower size restriction. The 2026 survey connects reconstruction to algebraic quantities unchanged by vertex renaming. Its proposed route seeks quantities that distinguish all original graphs from their decks, rather than only a few recoverable statistics.[1]