$\displaystyle\binom{F_2}{F_1} = \displaystyle\binom{Y}{X} = \displaystyle\binom{H+Y}{H+X} = \displaystyle\binom{f(F_2)}{f(F_1)}$.

3.  $F_2 = G+Z$, $v(Z) < v(G)$, but $F_1$ has no component isomorphic to $G$. In this case, any realisation of $F_1$ as an induced subgraph of $F_2$ may be represented (possibly in many ways) as $F_1 = X+Y$ where $X$ is an induced proper subgraph of the component $G$ of $F_2$ and $Y$ is an induced subgraph of $Z$. Moreover, $v(X) < v(G)$ and $v(Y) < v(G)$. Since $\displaystyle\binom{G}{X} = \displaystyle\binom{H}{X}$, we have $\displaystyle\binom{G+Z}{F_1} = \displaystyle\binom{H+Z}{f(F_1)}$. Note that the actual value of $\displaystyle\binom{F_2}{F_1}$ may be written by considering all possible ways of realising $F_1$ as an induced subgraph of $G+Z$.

Thus we have shown Equation (\[eq-2g2h\]) for arbitrary non-empty induced subgraphs of $2G$, which implies the result.

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

The [*only if*]{} part follows from Proposition \[prop:equiv-un\]. The [*if*]{} part is proved by contradiction. Suppose $G$ and $H$ are connected nonisomorphic graphs with the same vertex deck, that is, they are a counter example to Ulam’s conjecture. Then $2G$ and $2H$ are nonisomorphic but $\mathcal{N}(2G) = \mathcal{N}(2H)$ by Lemma \[lem-2g2h\]. Therefore, $2G$ and $2H$ are 