Kelly's Proof Of Reconstruction Conjecture For Trees

386 Views Asked by At

The vertex reconstruction conjecture states that a graph on n>2 vertices can be discovered from only knowing its proper induced subgraphs.

Kelly proved this for trees in 1961. I saw his proof and I was asking the question: is his original proof still the only or simplest out there?

1

There are 1 best solutions below

1
On BEST ANSWER

Actually, I found this survey by Bondy and Hemminger: "Graph Reconstruction: A Survey", where they give a significantly smaller proof on trees using a "Counting Lemma" generalising "Kelly's Lemma".