 Solution

Use the back-and-forth method. Enumerate the two domains without repetitions as $a_0,a_1,\dots$ and $b_0,b_1,\dots$. We construct a sequence of finite maps, each a partial isomorphism of structures,starting with the empty function. Each $f_s$ is a bijection between finite subsets of the domains and preserves both adjacency and nonadjacency on its domain.

At a forth step, choose the first $a_i$ outside the current domain. List the finitely many domain vertices as $u_1,\dots ,u_r$. In $\mathcal{B}$, prescribe that the new image $b$ be adjacent to $f_s(u_j)$ exactly when $a_i$ is adjacent to $u_j$ in $\mathcal{A}$. Since the image vertices are distinct, an extension axiom in $\mathcal{B}$ supplies such a $b$ outside the entire current range. Extend $f_s$ by $a_i\mapsto b$. This preserves injectivity, adjacency and nonadjacency, including the absence of loops.

At a back step, choose the first $b_i$ outside the current range. Apply the same argument to the inverse partial isomorphism of structures in $\mathcal{A}$, finding a fresh preimage with the required adjacency pattern to the current domain. Extend $f_s$ by this new pair. Alternate forth and back steps indefinitely.

DefineBecause each finite function extends the preceding one, this is a well-defined injective function. The forth steps eventually include every $a_i$ in its domain, and the back steps eventually include every $b_i$ in its range, so $f$ is a bijection. Given any $u,v$, both lie in the domain of some finite $f_s$, where the edge equivalence already holds. It therefore also holds for $f$:Thus the two first-order structures are isomorphic. Alternating the steps is essential for surjectivity: repeatedly extending only the domain would merely construct an embedding into $\mathcal{B}$.