Correction of a proof on the ally-reconstruction number of a disconnected graph

Abstract. The paper [2] claimed that a disconnected graph with at least two nonisomorphic components is determined by some three of its vertex deleted subgraphs. While this statement is true, the proof in [2] is incorrect. We give a correct proof of this fact. In this paper all graphs are finite, simple and undirected. If G is a graph and v is a vertex of G then we refer to the graph G − v obtained by deleting v from G as a vertex deleted subgraph of G. The collection of all vertex deleted subgraphs of G is called the deck of G, which is denoted by D(G), and the elements of D(G) are referred to as cards. A graph that is determined up to isomorphism by its deck is said to be reconstructible, and it is conjectured that all graphs with at least three vertices are recon-structible. For an excellent survey paper on graph reconstruction we refer the reader to [1]. The ally-reconstruction number of a reconstructible graph is the minimum number of cards needed to reconstruct that graph. In [2] Myrvold claimed that the ally-reconstruction number of a disconnected graph with at least two nonisomorphic components is three. While this fact is true the proof in [2] is incorrect. In this paper we give a correct proof of this fact. Let G be a graph with at least two nonisomorphic components. Myr-vold’s proof [2, Lemma 2] instructs us to pick three vertices from G as follows. If G has at least two different component orders then pick u to be a non-cutvertex from a component of maximum order and v to be a non-cutvertex from a component of minimum order. Also, if it is possible to pick u in such a way that deleting u from the large component results in a component isomorphic to the one that v lies in, then pick u in this way. Then pick a third vertex w so that G−w has at least as many components as any other vertex deleted subgraph of G. It is claimed that G − v, G − u and G − w determine G. Now it is true that if H is a graph with cards isomorphic to these and if H has the same number of components as G then G and H must be isomorphic. But the following example shows that the cards alone do not determine G, and thus the problem arises from assuming 1 that the number of components is reconstructible from these cards. u v w u ' v' w&apos