show/hide this revision's text 3 order -- degree

Stefan's original idea is realized in the following observation, which shows that one $\mathbb{Z}$-chain is elementary equivalent to two such chains.

Theorem. The theory of nontrivial cycle-free graphs where every vertex has order degree $2$ is complete.

Proof. All models of uncountable size $\kappa$ consist of $\kappa$ many $Z$ \mathbb{Z}$ chains, and hence are isomorphic. Thus, the theory is $\kappa$-categorical, and hence complete. QED

Thus, all cycle-free graphs with every vertex of order degree $2$ have the same first order theory. In particular, the graph consisting of one $Z$-chain \mathbb{Z}$-chain is elementary equivalent to the graph consisting of any number of such $Z$ \mathbb{Z}$ chains. Since the first graph is connected and the latter are not, it follows that neither connectivity nor disconnectivity are first-order expressible as theories in the language of graph theory.
show/hide this revision's text 2 added 11 characters in body

Stefan's original idea is realized in the following observation.

Theorem. The theory of nontrivial cycle-free graphs where every vertex has order $2$ is complete.

Proof. All models of uncountable size $\kappa$ consist of $\kappa$ many $Z$ chains, and hence are isomorphic. Thus, the theory is $\kappa$-categorical, and hence complete. QED

Thus, all cycle-free graphs with every vertex of order $2$ have the same first order theory. In particular, the graph consisting of one $Z$-chain is elementary equivalent to the graph consisting of any number of such $Z$ chains. Since the first graph is connected and the latter are not, it follows that neither connectivity nor disconnectivity are first-order expressible as theories in the language of graph theory.
show/hide this revision's text 1

Stefan's original idea is realized in the following observation.

Theorem. The theory of cycle-free graphs where every vertex has order $2$ is complete.

Proof. All models of uncountable size $\kappa$ consist of $\kappa$ many $Z$ chains, and hence are isomorphic. Thus, the theory is $\kappa$-categorical, and hence complete. QED

Thus, all cycle-free graphs with every vertex of order $2$ have the same first order theory. In particular, the graph consisting of one $Z$-chain is elementary equivalent to the graph consisting of any number of such $Z$ chains. Since the first graph is connected and the latter are not, it follows that neither connectivity nor disconnectivity are first-order expressible as theories in the language of graph theory.