Math 2.0

Combinatorics Graph theory: basic notions Conjecture

Graph reconstruction conjecture

Builds on GraphInduced subgraphGraph isomorphism

Statement

For a finite graph GG and a vertex vv of GG, let G−vG - v be the induced subgraph on the vertices other than vv. The deck of GG is the multiset of the isomorphism classes of the graphs G−vG - v, one for each vertex vv. Conjecture: if GG and HH are finite graphs with at least 33 vertices and the same deck, then GG and HH are isomorphic.

Remarks

The bound on the number of vertices is needed. The graph with 22 vertices and one edge and the graph with 22 vertices and no edge have the same deck, made of two single vertices. The conjecture is due to Kelly and Ulam, and it is open. Many invariants can be read off the deck, for example the number of edges and the degree sequence. Several classes of graphs are known to be reconstructible from their decks, among them regular graphs, disconnected graphs and trees. Computer searches have confirmed the conjecture for all graphs with few vertices.

Reading path

To understand this page from the ground up, read these 5 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionGraph isomorphism, definition, no evidence levelGraph isomorphismdefinitionSubgraph, definition, no evidence levelSubgraphdefinitionInduced subgraph, definition, no evidence levelInduced subgraphdefinitionGraph reconstruction conjecture, conjecture, no evidence levelGraph reconstruction …conjecture
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Graph isomorphism definition
  3. Subgraph definition
  4. Induced subgraph definition
  5. Graph reconstruction conjecture conjecture

Further reading

  1. Web https://en.wikipedia.org/wiki/Reconstruction_conjecture
About this page
TagXRBPS2QYE3
URIm2://XRBPS2QYE3
Kindconjecture
WritingW0 stub
MSC05C60
StatusThis copy of the site has no build data. Run m2 status XRBPS2QYE3.
AboutGraph
UsesGraph, Induced subgraph, Graph isomorphism
Same as
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.