Theory T of graphs

Question

Consider the theory $T$ of graphs. How can I show that there is no theory $T' \supseteq T$ such that the models of $T'$ are exactly the connected graphs (i.e. the graphs for which for every pair of vertices there exists a path between them)?

Answer 1

The key fact is the compactness theorem: if $\Gamma$ is a collection of sentences, and every finite subset of $\Gamma$ has a model, then $\Gamma$ has a model.

Suppose $T'$ characterized the connected graphs. Consider the expansion of the language of graphs by two new constant symbols, $c, d$. Now let $\Gamma$ be $T'$ together with the sentences "there is no path of length $n$ connecting $c$ and $d$" for each $n$ (do you see why each such sentence is, in fact, expressible as a first-order sentence in the expanded language?).

Every finite subset of $\Gamma$ has a model (why?), so by compactness so does $\Gamma$. But can any model of $\Gamma$ be connected? (Think about $c$ and $d$ . . .)

So there's a model $M$ of $\Gamma$ which is undirected. But $M$ is also a model of $T'$, since $T'\subseteq \Gamma$ . . .

Answer 2

Suppose $T'$ is such a theory. Let $T''$ be the set of all sentences which are true in every cycle graph $C_n.$ Since the graphs $C_n$ are connected, they are models of $T',$ so we have $T'\subseteq T''.$ Since $T''$ has arbitrarily large finite models, by the Löwenheim–Skolem theorem $T''$ has an uncountable model $G,$ and $G$ is not connected. (Why not?) Since $G$ is also a model of $T,$ this contradicts the assumption that all models of $T'$ are connected. Moreover, $T''$ also has a countable model which is not connected. (Why?)