and then construct $\mathcal{N}(\Lambda_j)$, and assign it a multiplicity equal to the edge label on $\Lambda_I-\Lambda_j$.

[**Remark**]{} It is is possible that for distinct $j$ and $k$, the matrices $N(\Lambda_j)$ and $N(\Lambda_k)$ are equal. In this case a multiplicity $N_{Ij}$ is assigned to $N(\Lambda_j)$ and $N_{Ik}$ is assigned to $N(\Lambda_k)$ while constructing the above collection.

\[lem-empty\] Let $rK_1$ be the $r$-vertex empty graph. The number of induced subgraphs of $G$ isomorphic to $rK_1$ is determined by $\mathcal{N}(G)$.

The required number is $$\displaystyle\binom{G}{rK_1} = 
\displaystyle\binom{v(G)}{r} - \sum_{j\mid v(\Lambda_j) = r}N_{Ij}$$ where indices $j$ in the summation are determined by Lemma \[lem-num-vertices\].

We are interested in the question of reconstructing a graph $G$ or some of its invariants given $\mathcal{N}(G)$. As indicated earlier, we will assume that the induced subgraphs $\Lambda_i; i \in [1,I]$ are not given. We have the following relationship between Ulam’s conjecture and the $\mathcal{N}$-matrix reconstructibility.

\[prop:equiv-un\] Ulam’s conjecture is true if and only if all graphs on three or more vertices are $\mathcal{N}$-matrix reconstructible.

Proof of [*if*]{}: by Lemma \[lem-kelly1\], $\mathcal{N}(G)$ is constructed from $\mathcal{VD}(G)$. Therefore, Ulam’s conjecture is true if all graphs are $\mathcal{N}$-matrix reconstructible. In fact, a graph is reconstructible if it is $\mathcal{N}$-matrix reconstructible.

Proof 