Small Graphs are Reconstructible

by Derrick Stolee

One of the most famous examples of using canonical deletion was McKay’s method to verify (for small graphs) one of the oldest open problems in graph theory: the Reconstruction Conjecture. This is a natural example to discuss the benefits of canonical deletion for two reasons:

  1. It uses vertex augmentations/deletions as in our standard examples.
  2. By slightly customizing the canonical deletion, we can significantly improve the running time over simply generating graphs and testing the conjecture on all pairs.

The Reconstruction Conjecture

The Reconstruction Conjecture hardly needs an introduction to any audience patient enough to read this blog, but let’s go over the basics for the sake of completeness. Just know that this problem was originally posed by Kelly and Ulam as something to play with while building the atomic bomb (at least in Ulam’s case). It’s that old.

Given a graph G, its deck is the (multi)set of isomorphism classes of graphs H such that H is isomorphic to a vertex-deleted subgraph G - v. Each isomorphism class is called a card and the multiplicity of a card H is how many vertices v \in V(G) have H \cong G-v. Every graph has a deck, but is that deck uniquely determined? If G has only two vertices, the deck is a pair of isolated vertices, so we cannot tell if G is empty or complete. What happens for three or more vertices?

The Reconstruction Conjecture: All graphs on at least three vertices are determined (up to isomorphism) by their deck.

The Reconstruction Conjecture (Alternate): If G and G' have isomorphic decks, then G \cong G'.

A stronger form of the conjecture removes the multiplicity of the cards and simply asks for the isomorphism classes which appear as vertex-deleted subgraphs (but at least four vertices are required). In this form, a vertex-transitive graph would have only one card in its deck. McKay’s strategy also confirmed this stronger form of the conjecture.

Lots of different cases of the Reconstruction Conjecture are known to hold and I will not discuss them here. However, one simple case is that disconnected graphs are reconstructible, so we will restrict to testing connected graphs.

Testing the Conjecture

To test the conjecture for a given number n of vertices, we could “simply” generate all graphs of order n and pairwise compare their decks. This would not require a lot of new programming, since we already have geng to generate graphs. The problem lies in the pairwise comparison, since there are a lot of graphs and testing all pairs would be an even harder task than generating the graphs.

McKay takes the approach of using the generation tree to his advantage. He observed that vertex-deleted subgraphs are very closely related to the deletions used when generating graphs by vertices. The following point is so important I will make it bold:

By selecting a canonical deletion using only the deck, any pair of non-isomorphic graphs with isomorphic decks would appear as augmentations to the same graph.

So, if there is a pair G \not\cong G' of graphs of order n, they are both augmentations of a common vertex-deleted subgraph H of order n-1. Since there are 1,006,700,565 unlabeled connected graphs of order 11 and 11,716,571 of order 10, and therefore there will be an average of about 86 graphs of order 11 “above” a given graph of order 10. Testing all pairs of these 86 graphs is not much harder than generating them all; certainly is a significant improvement over testing all pairs among the full list of 11 million graphs.

As far as performing the testing between a pair G, G', we can first compare certain reconstructible invariants of the graphs, such as the degree sequences, to determine the decks will be different. McKay used a complicated numerical invariant based on several reconstructible parameters to hopefully differentiate two graphs with non-isomorphic decks. Very rarely, the decks were explicitly compared for isomorphism using canonical labelings.

The Canonical Deletion

It remains to discuss how to generate a canonical deletion from the deck. Recall that a canonical deletion in the case of vertex augmentations/deletions is to select a vertex v = {\mathrm{del}}(G) in the graph G up to vertex orbits. That way, any graph G' isomorphic go G would select a vertex v' such that there is an isomorphism from G to G' sending v to v'. We will select such a vertex such that if G' has an isomorphic deck, then G-v is isomorphic to G'-v'.

We can begin by filtering the deck using some reconstructible invariants. For example, by selecting a vertex of minimum degree, we are selecting a card with maximum number of edges. After performing a few of these filters, we may end up with a unique card, or we may have several cards to select. By using the canonical labeling of these graphs, we can select the card with lexicographically-least adjacency matrix (for example).

This process now selects the card we will use in the deletion and thus is sufficient for the comparison between graphs with isomorphic decks. However, there is a very subtle point that is very important for the properties of a canonical deletion in order to avoid generating an isomorphism class of graphs multiple times:

There exist graphs G with vertices u,v \in V(G) such that G-v \cong G-u but u and v are not in the same orbit!

Therefore, selecting a canonical deletion based only on the deck is not always completely possible! Specifically, we cannot determine which vertex orbit the selected card H came from as a vertex-deleted subgraph. However, it suffices to select from among the vertices v such that G - v\cong H. We can use the canonical labeling to finish the job in this case.

Results

Using this technique and restricting to certain classes of graphs, McKay was able to show the following graphs have no counterexample to the Strong Reconstruction Conjecture:

Class Orders
Connected Graphs 4-11
Max Degree at most 5 12
Triangle-free 4-14
Square-free 4-15
Bipartite 4-15
Bipartite and Max Degree at most 5 16

So what can be done now? There is definitely an issue with the number of graphs of order 13 that may not be reachable, but with today’s computers could we test all graphs of order 12? (McKay did his search before 1998.) If someone would repeat the experiment, I would report it here on the blog.

Some advice: notice that the canonical deletion I described only needs to be performed at the last augmentation step, from n-1 vertices to n vertices. Therefore, you could generate all graphs of order n-1 using geng and load those graphs into your program and extend in all possible ways. Likely, that would be the fastest method to test the graphs of order n. If you wrote all the graphs of order 11 to a file, then split that file into many parts, you could very easily parallelize the test without much problem. Another recommendation: we can also restrict to 2-connected graphs, since Yang proved that all graphs of order n are reconstructible if all 2-connected graphs of order n are reconstructible.

See Also

Introduction to Canonical Deletion

References

B. D. McKay. Small graphs are reconstructible. Australasian Journal of Combinatorics, 15:123-126, 1997.

B. D. McKay. Isomorph-free exhaustive generation. J. Algorithms, 26(2):306-324, 1998.

Y. Z. Yang. The reconstruction conjecture is true if all 2-connected graphs are reconstructible. J. Graph Theory, 12(2):237-243, 1988.

Advertisements