Is it known whether all graphs having trivial automorphism group are vertex reconstructible? And if so, what is the proof?


2 Answers 2


Consider the following passage from [1]:

As pointed out in [22], graphs which are asymmetric should be easier to reconstruct, yet symmetric graphs (even those which are at least regular), which should present a stiffer challenge, are simple to reconstruct.

From that sentence, I would draw the conclusion that the reconstructibilty of asymmetric graphs was still not known to the authors of that survey in 2006.

While it is possible that further advancements have been made in the intervening years (or that the authors of that article were simply unaware of the result), the fact that none of the usual searches (including synonyms of the term "asymmetric graph" like "rigid" or "trivial automorphism group") turns up anything conclusive on the topic is a little suspicious. Of course, the absence of evidence is not necessarily any proof of absence but in my opinion, such a result would be of such significance (a blockbuster result, one might say) that the article that proved it should be very, very easy to find.

A few more recent sources that appear to omit mention of any result regarding the reconstructibility of asymmetric graphs are [2] and [3].

  1. Asciak, K., et al. "A survey of some open questions in reconstruction numbers." Preprint (2006).

  2. Hartke, Stephen G., et al. "Automorphism groups of a graph and a vertex-deleted subgraph." the electronic journal of combinatorics 17.1 (2010): R134.

  3. Lauri, Josef, and Raffaele Scapellato. Topics in graph automorphisms and reconstruction. Cambridge University Press, 2003.


By a well known theorem of Erdös, the smallest non-trivial asymmetric graphs have V(G)=6. The Reconstruction Conjecture states that all finite graphs with 3 vertices or more are vertex reconstructible. So the vertex reconstructability of nontrivial, finite asymmetric graphs is entirely contingent on this fundamental, and yet unproved, result. The question of wether asymmetric graphs are all vertex reconstructible is essentially an iteration of the Reconstruction Conjecture itself.

  • 2
    $\begingroup$ I'm not sure I understand the logic here. The OP is asking if a special case of the reconstruction conjecture is known to be true. That the conjecture in the general case is still unsolved does not mean that it is not solved for this special case. $\endgroup$
    – Casteels
    Jul 25, 2015 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.