The Graph Reconstruction Conjecture - Numberphile

Key Concepts

• Graph Reconstruction Conjecture: The conjecture states that a graph can be uniquely determined (up to isomorphism) from its deck of vertex-deleted subgraphs.
• Graph: A collection of vertices (dots) and edges (lines) connecting them.
• Vertex: A dot in a graph.
• Edge: A line connecting two vertices.
• Subgraph: A graph formed by a subset of vertices and edges of a larger graph.
• Vertex-Deleted Subgraph: A subgraph obtained by removing a single vertex and all incident edges from the original graph.
• Deck: The collection of all vertex-deleted subgraphs of a graph.
• Isomorphism: Two graphs are isomorphic if they are structurally identical, meaning there's a one-to-one correspondence between their vertices and edges that preserves adjacency.
• Legitimate Deck: A collection of subgraphs that can be formed by deleting one vertex at a time from some graph.
• Illegitimate Deck: A collection of subgraphs that cannot be formed by deleting one vertex at a time from any graph.
• Degree of a Vertex: The number of edges connected to a vertex.
• Regular Graph: A graph where every vertex has the same degree.
• Tree: A connected graph with no cycles.
• Planar Graph: A graph that can be drawn on a plane such that no edges cross each other.
• Oriented Graph (Digraph): A graph where each edge has a direction.
• Tournament: A complete oriented graph on a set of vertices where for every pair of distinct vertices, there is exactly one directed edge between them.
• Set Reconstruction Problem: A variation of the conjecture where the deck is a set (no duplicate subgraphs allowed).
• Extremal Problem: Problems that ask for the maximum or minimum number of elements (in this case, cards) needed to satisfy certain conditions.

The Graph Reconstruction Conjecture

The discussion centers around the Graph Reconstruction Conjecture, an unsolved problem in graph theory. The core idea is to determine if a graph can be uniquely identified from a collection of its "cards," which are obtained by systematically removing each vertex and its associated edges.

1. Understanding the Process of Creating a Deck

The process begins with an original graph, composed of vertices and edges. To create the "deck" of cards, each vertex is removed one by one. When a vertex is removed, all edges connected to it are also removed. This results in a set of subgraphs, each missing one vertex from the original graph.

Example: The speaker illustrates this with a simple graph. Removing each of the four vertices results in four subgraphs. The speaker refers to these subgraphs as "cards" and the entire collection as a "deck."

2. Recoverable Information from a Deck

Several pieces of information about the original graph can be deduced from its deck:

• Number of Vertices: This is straightforward. The number of vertices in the original graph is equal to the number of cards in the deck, or alternatively, the number of vertices in any single subgraph plus one.
  • Formula: Number of vertices = Number of cards = (Number of vertices in a subgraph) + 1.
• Number of Edges: This requires a bit more calculation. Each edge in the original graph is connected to two vertices. Therefore, when a vertex is removed, the edge connected to it is also removed. This means each edge will be "lost" twice during the deck creation process (once for each of its endpoints). By summing the number of edges in all the cards and dividing by the number of times each edge is counted (which is the total number of vertices minus two), the original number of edges can be determined.
  • Formula: Number of edges = (Sum of edges in all cards) / (Total number of vertices - 2).
  • Example: For a graph with 4 vertices and 8 edges in total across all cards, the number of edges is 8 / (4 - 2) = 8 / 2 = 4 edges.
• Sequence of Degrees: The degree of a vertex is the number of edges connected to it. The sequence of degrees of all vertices in the original graph can also be inferred. For each card, the degree of the missing vertex can be calculated by subtracting the number of edges present in the subgraph from the total number of edges in the original graph.
  • Example: If the original graph has 4 vertices and 4 edges, and a card shows a subgraph with 2 edges, the missing vertex must have had a degree of 4 (total edges) - 2 (edges in subgraph) = 2.

3. The Core Question: Uniqueness and Reconstruction

The Graph Reconstruction Conjecture is not just about being able to reconstruct a graph from a deck, but about whether that reconstruction is unique. The conjecture states: "Given a deck of cards that belongs to a graph, can you reconstruct the original graph uniquely (up to isomorphism)?"

• Reconstructible Graph: A graph is considered reconstructible if its deck allows for a unique reconstruction.
• The "Burning Question": The central unsolved problem is whether every legitimate deck corresponds to one and only one graph.

4. Legitimate vs. Illegitimate Decks

A crucial aspect of the conjecture is identifying whether a given collection of subgraphs is a "legitimate deck" – meaning it could have been generated from some graph.

• Identifying Illegitimate Decks: Simple checks can reveal illegitimate decks:
  • Inconsistent Number of Vertices: If the number of vertices in the subgraphs is not consistent (e.g., some have 3 vertices, others have 4, when the number of cards suggests a different original vertex count), it's an illegitimate deck.
  • Inconsistent Number of Edges: If the calculation for the number of edges yields a result that is impossible given the subgraphs (e.g., more edges in a subgraph than the calculated total for the original graph), it's illegitimate.
  • Example of Illegitimate Deck: A collection of five cards, each with four vertices, is presented. The number of vertices in the original graph would be 5. Summing the edges (3+25+2+2+6 = 18) and dividing by (5-2=3) gives 6 edges. However, one card has 6 edges, which is impossible if the original graph only had 6 edges in total.

5. Progress and Known Results

The conjecture was first stated around the late 1950s, with Kelly and Ulam being key figures. While the general conjecture remains unsolved, progress has been made for specific classes of graphs:

• Regular Graphs: These are easily reconstructible. If a deck consists of identical cards, it strongly suggests a regular graph. The speaker demonstrates how to reconstruct a regular graph by identifying its degree and then systematically adding the missing vertex and edges.
  • Two-Step Proof for Regular Graphs:
    1. Recognize the Class: Identify that the graph is regular from the deck.
    2. Reconstruct: Use the knowledge of regularity to uniquely reconstruct the graph.
• Trees: Graphs with no cycles are also reconstructible.
• Complete Graphs: These are also relatively easy to reconstruct.

However, for many other important classes of graphs, such as planar graphs, the conjecture is not fully resolved. For these, researchers might only be able to complete one of the two steps (recognizing the class or reconstructing the graph).

6. Variations and Related Problems

The complexity of the conjecture has led to the exploration of related problems and variations:

• Oriented Graphs (Digraphs): For oriented graphs, counterexamples to the reconstruction conjecture have been found. For instance, certain tournaments on five vertices can have decks that are identical to other oriented graphs, disproving the conjecture for this specific type.
• Set Reconstruction Problem: This variation considers decks where duplicate subgraphs are not allowed. It's still an open problem.
• Extremal Problems: These questions explore the minimum or maximum number of cards needed to uniquely reconstruct a graph. This involves understanding which graphs are "hardest" to reconstruct and how many cards are necessary to distinguish between them.
  • Example: A disconnected graph with two triangles is used to illustrate how identical cards can make reconstruction difficult. If only four identical cards are provided, it might be indistinguishable from another graph that produces four identical cards and two different ones. This highlights the need for a sufficient number of cards to ensure uniqueness.

7. The "Rabbit Hole" of Related Questions

The speaker emphasizes that the Graph Reconstruction Conjecture is a "constellation of problems." Exploring it leads to numerous tangent questions, such as:

• What if we removed edges instead of vertices?
• How many cards are truly necessary for reconstruction?
• Can we reconstruct from an incomplete deck?

These related problems, while not directly solving the main conjecture, offer insights and can be seen as "nerdy games" that help understand the underlying principles.

8. Conclusion and Current Status

The Graph Reconstruction Conjecture remains a significant open problem in graph theory. While progress has been made for specific graph classes, a general proof or a definitive counterexample for all graphs is still elusive. The exploration of related problems and variations continues to be an active area of research, driven by the inherent beauty and complexity of the conjecture. The speaker expresses personal fascination with the problem due to its rich landscape of interconnected questions.