I think this is a really neat exercise. At first, it seems that this is impossible. Indeed, $\mathfrak{A}$ is a “model” of the following sentence “$\forall a\forall b\exists p_{0},\ldots,p_{n}$ such that $<p_{0},p_{1},...,p_{n}>$ is a path connecting $a$ and $b$ ” (where we can formally write down what the last part means). Hence, every structure “equivalent” to $\mathfrak{A}$ must be a model of this sentence as well, meaning that it must be connected (as the sentence is simply the definition of connectedness). However, what breaks here, is that the sentence is not a first-order sentence. The problem is that it involves the existence of an arbitrary number of variables, which may be different for different $a$ and $b$ , and, more importantly, it can be greater than any fixed $n$ (so, for example, if $|\mathfrak{A}|$ were finite, every elementarily equivalent structure would be connected). What is implicitly missing in the sentence, is $\exists n$ , but this is not a valid part of the first-order language. Therefore, we cannot express connectedness in one or, equivalently, any finite number of sentences. We know, that for any pair $a$ and $b$ , it will satisfy all but finite number of wffs saying that $a$ and $b$ are connected by a path of length at most $n$ , but there is always a pair that does not satisfy any particular such wff. Therefore, $\mathfrak{A}$ fails to be a model of the generalization of any such sentence.

We can look at the problem from the other direction. Namely, as we said, the existence of an elementarily equivalent $\mathfrak{B}$ which is not connected is due to $\mathfrak{A}$ being an infinite structure. Therefore, for any sentence $\sigma_{n}$ saying that there are points $a$ and $b$ that are not connected by any path of length $n$ (which is just the negation of the generalizations of the sentences mentioned in the previous paragraph), i.e. for any $\sigma_{n}$ being $\exists c\exists d\tau_{n}$ , where $\tau_{n}$ is $$\begin{eqnarray*} \forall v_{0}\ldots\forall v_{n} & & v_{0}=c\rightarrow(\neg v_{0}=v_{1}\rightarrow Pv_{0}v_{1})\rightarrow\ldots\\ & & \ldots\rightarrow(\neg v_{n-1}=v_{n}\rightarrow Pv_{n-1}v_{n})\rightarrow\neg v_{n}=d, \end{eqnarray*}$$ $\mathfrak{A}$ is a model. And $\mathfrak{A}$ is a model of the set $\Gamma$ of all such sentences.

Now, as suggested, we extend the language by adding constant symbols $c$ and $d$ , so that each $\tau_{n}$ is now a sentence of the language ($c$ and $d$ are now constant symbols rather than variables, and $\sigma_{n}$ ’s are not wffs in the new language). The structure $\mathfrak{A}_{ij}$ , which is $\mathfrak{A}$ with $c^{\mathfrak{A}_{ij}}=i$ and $d^{\mathfrak{A}_{ij}}=j$ , is a model of $\tau_{n}$ iff $|i-j|>n$ . Moreover, $\mathfrak{A}$ is a model of a sentence $\sigma$ not using constant symbols $c$ and $d$ iff $\mathfrak{A}_{ij}$ is a model of $\sigma$ (this can be shown directly, by induction). Therefore, if we consider the set of sentences $\Gamma=\mbox{Th}\mathfrak{A}\cup\{\tau_{n}\}_{n\in\mathbb{N}}$ ($\mbox{Th}$ was introduced in Exercise 26 of Section 2.2, and is formally defined on page 148), then every finite subset $\Gamma_{0}$ of $\Gamma$ has a model (we just find the maximum $n$ such that $\tau_{n-1}\in\Gamma_{0}$ and take $\mathfrak{A}_{0n}$ ). By the compactness theorem, $\Gamma$ has a model, $\mathfrak{B}'$ . Let $\mathfrak{B}$ be the restriction of $\mathfrak{B}'$ to the original language. Now, if $\mathfrak{A}$ is a model of a sentence $\sigma$ (which does not use constant symbols) then $\sigma\in\mbox{Th}\mathfrak{A}$ and $\Gamma\vdash\sigma$ . Then, there is a deduction of $\sigma$ from $\Gamma$ which does not use constant symbols (for example, we can proof this using rule EI), and, hence, $\mathfrak{B}$ proves $\sigma$ , implying $\sigma\in\mbox{Th}\mathfrak{B}$ . Vice versa, if $\sigma\notin\mbox{Th}\mathfrak{A}$ , then $\neg\sigma\in\mbox{Th}\mathfrak{A}$ , $\neg\sigma\in\mbox{Th}\mathfrak{B}$ , $\sigma\notin\mbox{Th}\mathfrak{B}$ . Overall, $\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent (another way is just to use Exercise 26(a) of Section 2.2 by noting that $\mathfrak{B}$ models $\mbox{Th}\mathfrak{A}$ ).

To see that $\mathfrak{B}$ is not connected, we note that it is connected iff $\mathfrak{B}'$ is connected (the connectedness has nothing to do with constant symbols, and deals only with the underlying structure, i.e. the universe and relation $P$ ), and if $c^{\mathfrak{B}'}$ and $d^{\mathfrak{B}'}$ were connected by a path of length $n$ , $\mathfrak{B}'$ would not be a model of $\tau_{n}$ .