Graphs and first-order logic.

Quote:

We define the distance $\displaystyle d(a,\,b)$ between two vertices $\displaystyle a$ and $\displaystyle b$ of a graph as the least number of edges in a path from $\displaystyle a$ to $\displaystyle b.$ If no such path exists, then $\displaystyle d(a,\,b)=\infty.$ ... $\displaystyle \nu_G$ is the vocabulary of graphs.

...

(b) Does there exist a $\displaystyle \nu_G-$formula $\displaystyle \delta_{\infty}(a,\,b)$ so that, for any graph $\displaystyle G$, $\displaystyle G\models\delta_{\infty}(a,\,b)$ if and only if $\displaystyle d(a,\,b)=\infty$? Explain your answer.

I said no, because if there were such a formula, then there would be a formula saying that a graph is connected. What is your opinion?

Re: Graphs and first-order logic.

I agree. And connectedness is not expressible *in first-order logic* by compactness argument.