Define a sentence that has arbitrarily large finite models

Question

I am trying to solve these problems :

(a) Define a $V_G$-sentence $\phi$ such that $\phi$ has arbitrarily large finite models, and for any model $G$, $G$ is a connected graph.

(b) Find a connected graph that does not model the sentence $\phi$ you found in (a).

Any ideas?

Answer 1

The proof that graph connectedness is not expressible in the first-order language of graphs is a classic application of compactness. The purpose of this exercise is to show that a first-order sentence in the language of graphs may only have connected models, as long as it excludes some connected graphs as well.

This observation suggests how to proceed. A sentence about graphs that has connected models of arbitrary size is one that characterizes complete (simple) graphs. If $E$ is the edge relation, then

$$ \forall x \,.\, \neg E(x,x) \wedge \forall y \,.\, x=y \vee E(x,y) \enspace.$$

Every connected but incomplete graph is not a model of this sentence.