The Reconstruction Conjecture Let G be a graph on at least three vertices and v be a vertex of G . Then G-v is a vertex deleted subgraph of G . Thus, the deck for a graph on n vertices consists of n graphs, each of which has n-1 vertices. Each of graphs in this deck could be called a card . Given a deck of a graph G , certain parameters of G are easily determined.
G has one more vertex than any graph in the deck.
Every edge of G is missing from exactly two cards, thus each edge shows up on n-2 cards. The number of G can be determined by summing the numbers of edges on each card and dividing the total by n-2 . A parameter of G which can be deduced from the deck is called reconstructible . Since, the number of edges of G is reconstructible, the degree sequence of G is reconstructible. Thus, if G is a regular graph, G itself is reconstructible.