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. The collection of vertex deleted (unlabelled) subgraphs of G, together with their multiplicities, is the deck 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.

Similarly, for any graph H on fewer vertices than G, the number of subgraphs of G which are isomorphic to H can be determined by summing the numbers of such subgraphs on each card and dividing the result by |V(G)|-|V(H)|. (Kelly's Lemma)

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.

Disconnected graphs are reconstructible. Trees are reconstructible. Separable graphs without endvertices are reconstructible.

In 1967, Tutte proved that the dichromatic (rank) and Tutte (dichromate) polynomials are reconstructible. Years later, he heard in a lecture that the characteristic polynomial and chromatic number were not known to be reconstructible. The chromatic polynomial, chromatic number, the flow polynomial, and the number of spanning trees are easily deduced from the dichromatic polynomial; and Pouzet had shown that the only missing step in reconstructing the characteristic polynomial was counting the number of hamilton cycles. Tutte also showed how to count the Hamilton cycles. A similar polynomial, called the idiosyncratic polynomial is also reconstructible. In order to present the result in a way more people would understand, Tutte wrote a new paper in 1979. A few years later, W. Kocay gave a very simple proof using Kelly's Lemma, and I will try to outline that proof below, much as Tutte does in his 1998 book.
Some Readings

J.A.Bondy, A graph reconstruction manual, Surveys in Combinatorics, LMS-Lecture Note Series 166(1991) (Edited by A.D. Keedwell), 221-252.

J.A. Bondy and R.L. Hemminger, Graph reconstruction - a survey. Journal of Graph Theory 1(1977), 227-268.

D.L. Greenwell and R.L. Hemminger, Reconstructing the n-connected components of a grap, Aequationes Mathematicae 9(1973), 19-22.

A.J. Schwenk (Almost all trees are cospectral. New Directions in the Theory of Graphs. Academic Press, 1973, pages 275-307.) proved that, for almost every tree, there is another tree with the same characteristic polynomial. Such pairs of trees must also have the same Tutte polynomial. Thus, the Tutte polynomial and the characteristic polynomial together are not enough to characterize a graph. Here's one pair of co-spectral trees (Marshall, 1971) given as edge lists: 12,13,14,15,16,67,78 and 12,13,14,15,56,57,58. (Trees are reconstructible. It would be better to have examples of cospectral 2-connected graphs with the same rank polynomial.)

W.T. Tutte, On dichromatic polynomials, Journal of Combinatorial Theory 2(1967), 310-320.

W.T. Tutte, All the King's horses, Graph Theory and related Topics (1979) (Edited by J.A. Bondy and U.S.R. Murty), 15-33.

W.T. Tutte, Graph Theory as I Have Known it, Oxford Science Publications, Clarendon Press, Oxford, 1998. Chapter 9, pages 106-113.
Let s(F,G) denote the number of subgraphs of G which are isomorphic to F.

Kelly's Lemma. Suppose F has fewer vertices than G. Let s*(F,G) denote the sum of s(F,G-y), where the sum extends over all vertices y of G. Then, (v(G)-v(F)) s(F,G) = s*(F,G).

Proof. If H is a subgraph of G and H is isomorphic to F, then H occurs in (v(G)-v(F)) of the graphs G-y. Specifically, H is a subgraph of those G-y where y is not in V(H).
Kocay's Proof of Tutte's reconstruction of the dichromatic polynomial

Kelly's Lemma doesn't count subgraphs which are spanning. However, Kocay found a way to play a little trick on Kelly's Lemma in some cases. (Also, see the Greenwell and Hemminger Counting Theorem.)

Lemma. Let H and F be disjoint, connected graphs with v(H)+v(F)=v(G). The number of spanning subgraphs of G which are isomorphic to the union of H and F is reconstructible.

Proof. The number of ways of choosing a copy of H and a copy of F from among the subgraphs of G is s(F,G)s(H,G), but some of these pairs are not disjoint. However, if the copy of H and the copy of F are not disjoint, then their union L is a subgraph of some G-y. L can be written as a union of a copy of H and a copy of F in some number of ways, A(L;H,F). Summing the product s(G,L)A(L;H,F) over all of the possible isomorphism classes of L, we determine the number of non-disjoint pairs (H,F) of subgraphs. Subtraction from s(F,G)s(H,G) yields the number of disjoint (H,F) pairs.

Corollary. The number of spanning disconnected graphs isomorphic to a given graph is reconstructible.

Now, the dichromatic polynomial, Q(G;t,z) can be written as the sum of monomials N(r,s)trzs-n+r, where N(r,s) is the number of spanning subgraphs G:S of G with exactly r components and s edges, and n is the number of vertices of G.

We've just said that N(r,s) is reconstructible if r>1. But
N(1,s) + N(2,s) + ... + N(n,s) = C(|E|,s),
where C(|E|,s) is the number of ways to choose s edges from the edges of G. Thus, N(1,s) is reconstructible and, hence, all coefficients of Q(G;t,z) and Q(G;t,z) itself are reconstructible.

The chromatic polynomial, (-1)nQ(G;-m,-1), is reconstrucible. The flow polynomial, (-1)|E|+nQ(G;-1,-m), is reconstrucible. The dichromate, X(G;x,y)=(x-1)-r(G)Q(G;x-1,y-1), is reconstrucible. The number of spanning trees, X(G;1,1), is reconstrucible.

Still in the 1998 book, Tutte goes to explain that one can also reconstruct the number of pairs of non-separable subgraphs (H,F) of a loopless graph G with v(H)+v(F)=v(G)+1, and the the number of such pairs which meet at exactly one vertex, and then generalizes this to show that we can count the number of spanning separable subgraphs of G with a given number of edges. But we already know N(1,s), the number of spanning connected subgraphs with exactly s edges. From this we can find the number of non-separable spanning subgraphs of G with exactly s edges. When s=v(G), this is the number of Hamilton cycles.

Now, look at the characteristic polynomial, det(A-xI). The coefficient of xk is a sum of determinants of smaller principal submatrices if k>0, and is easily seen to be reconstructible. For k=0, we need the determinant of A. Look at the possible contributions: each contributing permutation corresponds to a subgraph consisting of components which are cycles or copies of K2. The contribution is determined by the isomorphism class of the subgraph, (-1)r(G:S) times the number of orientations of the cycles in G:S. The disconnected subgraphs we've already counted. The connected subgraphs are Hamilton cycles, which we've also counted. Thus, the characteristic polynomial is reconstructible.

If we replace the zeroes in A by some indeterminate Y, the determinant of this new matrix is the idiosyncratic polynomial of G. Tutte gave one more result: if the idiosyncratic polynomial is prime, then G is reconstructible, using Jacobi's Theorem on the minors of an adjugate matrix. And, for you statisticians: Bollobás proved that almost all graphs are reconstructible from just three of the cards in the deck.
Yair Caro suggests the following:

N.Alon, Y.Caro, I.Krasikov, Y.Roditty. Combinatorial reconstruction problems. JCTB 47(1989), 153-161. Yair Caro
Last modified January 15, 1999, by S.C. Locke. How to contact me.