Prove disconnectedness of a graph is not generalized first-order logic definable

Question

I have proved the connectedness of a graph is not generalized first-order logic definable. How about the disconnectedness? Is it also not first-order logic definable? (A property $\Phi$ of $\tau$-structures is generalized first-order definable iff there exists a set $T$ of sentences such that $A$ has property $\Phi$ is equivalent to that $A$ is a model of $T$)

Answer 1

Assume that the formula $\varphi$ is such that for any graph $\mathcal{G}$, $\mathcal{G}\models \varphi$ if and only if $\mathcal{G}$ is disconnected. Then we have that $\mathcal{G}\not\models \varphi$ if and only if $\mathcal{G}$ is not disconnected i.e. connected. Hence $\mathcal{G}\models \neg \varphi$ if and only if $\mathcal{G}$ is connected.

Thus as you have proven that connectedness isn't definable, we have shown that disconnectedness can't be either.

Answer 2

Let $G$ be a two-way infinite path, i.e., $G=(\mathbb Z,E)$ where $E=\{\{x,y\}:|x-y|=1\}.$ So $G$ is connected, while $2G$, the union of two disjoint copies of $G,$ is disconnected. You can use the Ehrenfeucht–Fraïssé back-and-forth method to prove that $G$ and $2G$ are elementarily equivalent. This shows that neither the class of connected graphs nor the class of disconnected graphs is definable by a set of first-order sentences.