It is a well-known conjecture of
S. M. Ulam that any finite graph of order at least three can be reconstructed from its
maximal vertex-deleted subgraphs. Formally (writing Gv for G − v) Ulam’sConjecture states: if G and H are finite graphs of order at least three such that there
is a bijection σ;V (G) → V (H) with the property (1) Gv≅Hσ(v) for all v ∈ V (G), then
G≅H. This conjecture has not been proved in general, although it was shown by P. J.
Kelly to be true for disconnected graphs and trees and has also been verified for
several other classes of graphs. The purpose of this paper is to examine
Ulam’s Conjecture for infinite graphs. (It is trivial to determine, from any
Gv, whether or not a graph G is infinite.) Results are obtained which can
loosely be viewed as extensions of Kelly’s work on disconnected graphs and
trees.
