Skip to main content

Chapter 40: Graph Reconstruction — The Whole from Parts

We conclude Part V with a fundamental question about information and structure. The Graph Reconstruction Conjecture asks whether a graph is determined by its vertex-deleted subgraphs—it is ψ = ψ(ψ) as structures knowing themselves through their parts, where the whole emerges uniquely from its fragments.

40.1 The Fortieth Movement: Holographic Structure​

Concluding our combinatorial cosmos:

  • We explored computation, matrices, sets, patterns, and synchronization
  • We end with reconstruction—the deepest self-reference
  • The transition to topology awaits

The Core Question: Is every graph uniquely determined by its collection of vertex-deleted subgraphs?

40.2 The Reconstruction Conjecture​

Definition 40.1 (Deck of a Graph): For graph G = (V, E) with |V| ≥ 3, the deck D(G) is: D(G)={G−v:v∈V}D(G) = \{G - v : v \in V\} where G - v is G with vertex v and incident edges removed.

Conjecture 40.1 (Kelly-Ulam, 1942): Any two graphs with isomorphic decks are isomorphic.

Status: Open for 80+ years!

40.3 Reconstructible Properties​

Definition 40.2 (Reconstructible Property): Property P is reconstructible if P(G) can be determined from D(G).

Theorem 40.1 (Various): Reconstructible properties include:

  • Number of vertices and edges
  • Degree sequence
  • Connectivity
  • Planarity
  • Chromatic number
  • Characteristic polynomial

Almost everything except the graph itself!

40.4 Reconstruction as ψ = ψ(ψ)​

Axiom 40.1 (Principle of Holographic Information): ψ=ψ(ψ)  ⟹  The whole is encoded in its parts\psi = \psi(\psi) \implies \text{The whole is encoded in its parts}

The reconstruction conjecture embodies:

  • Graphs knowing themselves through subgraphs
  • Local deletions preserving global information
  • The holographic principle in discrete form
  • This is ψ = ψ(ψ) as structural self-knowledge

40.5 Edge Reconstruction​

Stronger Version: Edge Reconstruction Conjecture.

Definition 40.3 (Edge Deck): DE(G)={G−e:e∈E}D_E(G) = \{G - e : e \in E\}

Theorem 40.2 (Harary): Edge reconstruction implies vertex reconstruction.

Progress: Proven for many more classes than vertex case.

40.6 Small Graphs Exception​

Why |V| ≥ 3?: Counterexamples for small graphs:

  • K₂ and 2K₁ have same 1-card deck
  • Must exclude trivial cases

Pattern: Reconstruction gets easier as graphs grow.

40.7 The Reconstruction Algorithm​

Kelly's Lemma: Number of copies of subgraph H in G can be computed from D(G).

Algorithm 40.1 (Reconstruction Attempt):

def reconstruct_from_deck(deck):
    n = len(deck) + 1  # Number of vertices
    
    # Count vertex degrees
    degree_sum = sum(card.num_edges() for card in deck)
    m = degree_sum // (n - 2)  # Number of edges
    
    # Reconstruct degree sequence
    degrees = []
    for i in range(n):
        # Degree of vertex i from cards not containing i
        deg_i = 2*m - sum_degrees_in_card(deck[i])
        degrees.append(deg_i)
    
    # Try to build graph with this degree sequence
    # checking consistency with deck...
    
    return candidate_graphs

Challenge: Multiple graphs may match constraints.

40.8 Reconstructible Classes​

Theorem 40.3 (Various): Reconstruction proven for:

  • Regular graphs
  • Trees
  • Disconnected graphs
  • Maximal planar graphs
  • Graphs with ≤ 11 vertices

Pattern: Structure helps reconstruction.

40.9 The Probabilistic Approach​

Theorem 40.4 (Bollobás): Almost all graphs are reconstructible.

Proof Idea: Random graphs have unique structure with high probability.

Paradox: Generic case easy, but proof elusive!

40.10 Ally Reconstruction​

Definition 40.4 (Ally): The ally of vertex v is N(v) ∪ {v}.

Ally Reconstruction: Determine G from allies of all vertices.

Result: Easier than vertex reconstruction, still open.

40.11 The New Digraph Conjecture​

For Directed Graphs: Reconstruction can fail!

Counterexample (Stockmeyer): Tournament on 4 vertices with non-unique reconstruction.

New Conjecture: Directed graphs with all in/out-degrees ≥ 2 are reconstructible.

40.12 Reconstruction Numbers​

Definition 40.5 (Reconstruction Number): rn(G)=min⁡{k:any k cards determine G}rn(G) = \min\{k : \text{any k cards determine } G\}

Question: How many cards suffice?

Known: rn(G) ≤ n - 1, often much smaller.

40.13 The Legitimate Deck Problem​

Inverse Problem: Given collection of graphs, is it a deck?

Theorem 40.5 (Manvel): Determining if collection forms valid deck is NP-complete.

Insight: Verification harder than reconstruction!

40.14 Spectral Reconstruction​

Approach: Use characteristic polynomials of cards.

Almost There: Spectrum almost determines graph.

Counterexamples: Cospectral non-isomorphic graphs exist.

Hope: Maybe deck spectra suffice?

40.15 The Endomorphism Approach​

Strategy: Reconstruct endomorphism monoid.

Theorem 40.6: If End(G) is reconstructible, then G is reconstructible.

Progress: Works for many classes.

40.16 Information Theory View​

Question: How much information in deck?

Entropy Analysis:

  • Full graph: ~n² log 2 bits
  • Deck: ~n³ log 2 bits
  • Massive redundancy!

Mystery: Why doesn't redundancy imply reconstruction?

40.17 Computer Verification​

Computational Progress:

  • All graphs ≤ 11 vertices: Verified
  • Special classes to larger sizes
  • No counterexample found

Limitation: Can't check all graphs.

Variants:

  1. Subgraph Reconstruction: From all subgraphs
  2. Induced Subgraph: Only induced subgraphs
  3. Switching Reconstruction: From switching classes
  4. Quantum Graphs: Reconstruction in quantum setting

Each illuminates different aspects.

40.19 Why Reconstruction Matters​

Fundamental Questions:

  1. How much determines structure?
  2. Is local information complete?
  3. When are parts equivalent to whole?
  4. Nature of mathematical information

Applications:

  • Network analysis
  • Chemical structure determination
  • Database recovery
  • Quantum information

40.20 The Fortieth Echo​

The Graph Reconstruction Conjecture perfectly concludes Part V:

  • Simple question hiding infinite depth
  • Almost all information reconstructible except identity
  • The mystery of the final step
  • Holographic principle in discrete mathematics

This is ψ = ψ(ψ) at its purest—structures attempting to know themselves through their vertex-deleted subgraphs. The conjecture claims that the collection of all (n-1)-vertex pieces uniquely determines the n-vertex whole.

As we close Part V, "Combinatorial Cosmos," we've journeyed through:

  • Computation's ultimate question (P vs NP)
  • Perfect balance in matrices (Hadamard)
  • Optimal intersection (Erdős-Ko-Rado)
  • Inevitable pattern (Ramsey)
  • Union closure mysteries (Union-Closed Sets)
  • Conquered complexity (Sensitivity)
  • Minimal synchronization (Cerny)
  • Holographic structure (Reconstruction)

Each revealed how discrete, finite structures contain infinite complexity when viewed through ψ = ψ(ψ).

The Reconstruction Conjecture declares: "I am the question of whether parts determine whole, whether removing each piece still leaves enough to rebuild, ψ = ψ(ψ) as structures encoding themselves holographically in their fragments. In my 80-year resistance lies the mystery of how the last bit of information—identity itself—hides even when all else is known."