Graphs and first-order logic.

Quote:

We define the distance

between two vertices

and

of a graph as the least number of edges in a path from

to

If no such path exists, then

...

is the vocabulary of graphs.

...

(b) Does there exist a

formula

so that, for any graph

,

if and only if

? 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.