Prove: if a graph is connected and the distances can be arbitrarily large, then it is an elementary submodel of a graph that is not connected.

Question

A path between two vertices a, b in a graph $(G, E)$ is a finite sequence $a = a_0 , . . . , a_n = b$ of vertices s.t. $\{a_i , a_{i+1} \} ∈ E$ for $i < n$, $n$ is the length of this path. A graph is connected iff for each pair of distinct vertices there exists a path between them. If a graph is connected, then the distance between two distinct vertices is the least length of paths between these two vertices.

Prove that: if a graph is connected and the distances between pairs of distinct vertices can be arbitrarily large, then it is an elementary submodel of a graph that is not connected.

Answer 1

Here is a sketch which will help you on the way:

1. For each $n<\omega$ find a formula $\varphi_n(x,y)$ which state that the distance between $x$ and $y$ is at least $n$.
2. Form the type $p(x,y)$ which is satisfied by two elements if and only if there is no path between x and y (note that you defined paths as finite).
3. Show that $p$ is a type of your graph $G$.
4. Use some standard theorem (Rothmaler 11.2.5. for instance) about types to show that there is an elementary extension $G'$ of $G$ which realize $p$.

Now you are done. Does this help?

Edit: Regarding 2. let $p(x,y) = \{\varphi_n(x,y): n\in\mathbb{N}\}$ and note that if $(a,b)$ realize $p$ then $\varphi_n(a,b)$ hold, thus the distance between $a$ and $b$ is at least $n$. But if this hold for each $n\in \mathbb{N}$ (which it has to for any realization of $p$) then the tuples distance can not be equal to any natural number, and thus there is no path between $a$ and $b$ (since paths are finite).

Edit2: Redgarding 3. In order to show that $p$ is a type of $G$ you need to show that $p$ is realized in some model of $T$, not necessarily in $G$ (and indeed $p$ is not realized in $G$). In order to show this one can use the compactness theorem and use the fact that each finite subset of $p$ is realized in $G$ to conclude that $p$ is consistent. If one wants to do this very formal one needs to add more constants and look at subsets of the theory of $G$ together with the type using these constants. (this is a quite standard method of proof which you should be able to find in the text book if necessary)