besagt im Prinzip, daß ein GraphG der Ordnung n eindeutig (bis auf Isomorphie) festliegt, falls die Struktur aller seiner induzierten Teilgraphen der Ordnung n – 1 bekannt ist.

Präzise formuliert lautet diese aus dem Jahre 1942 stammende Vermutung von P.J. Kelly und S.M. Ulam folgendermaßen:

Sind G und H zwei Graphen mit jeweils mindestens drei Ecken, und existiert eine bijektive Abbildung f : E(G) → E(H) so, daß G — v isomorph zu H — f(v) für jede Ecke v ∈ E(G) ist, so sind G und H isomorphe Graphen, in Zeichen G ≅ H.

Die beiden existierenden nicht isomorphen Graphen der Ordnung 2 zeigen, daß die Voraussetzung, daß G und H mindestens drei Ecken besitzen, für diese Vermutung notwendig ist.

Trotz großer Anstrengungen und bedeutender Teilerfolge konnte diese hochinteressante Vermutung bisher (2000) nicht bewiesen werden. Eines der schönsten Resultate stammt von Kelly selbst, der diese Vermutung 1957 für Bäume bestätigt hat.

Darüber hinaus ist die Vermutung auch für nicht zusammenhängende Graphen sowie für alle regulären Graphen richtig.

Im Jahre 1977 zeigte P.K.Stockmeyer, daß ein Ana- logon zur Rekonstruktionsvermutung für gerichtete Graphen nicht gilt.