I have met two similar exercises which I think can be solved by applying the compactness theorem.
- Let $G=(V,E)$ be a graph such that any vertex has finite degree, but we can find vertices of arbitrary high degree. Let $\kappa$ be an arbitrary large infinite cardinal. Show there is a graph $G'=(V',E')$ which has a vertex of degree $\kappa$ and $Th(G)=Th(G')$, i.e. the two graphs are elementary equivalent.
- Let $G=(V,E)$ be a graph such that any vertex has finite degree, but for any $n\in\omega$ we can find at least $n$ vertex of $G$ any of which has degree at least $n$. Let $\kappa$ be an arbitrary large infinite cardinal. Show there is a graph $G'=(V',E')$ which has at least $\kappa$ vertices of degree at least $\kappa$ and $Th(G)=Th(G')$, i.e. the two graphs are elementary equivalent.
My idea for the first point is: fix the language of graphs $\mathscr{L}=\{E\}$ and enrich it with a set of $\kappa$ new constants $C=\{c_i|i\in\kappa\}$, and yet anther new constant $\{v\}$.
Now let $\Sigma=Th(G)\cup Ax(i,j)\cup Ax(i)\;\;\;$ $i,j\in\kappa$
where $$Ax(i,j)=\lnot(c_i=c_j)\;\;\;\; Ax(i)=c_iEv$$
are ifinite axiom schema.
Now, $(G,V)$ is a model of every finite subtheory of $\Sigma$ and hence, by compactness, there is a model of $\Sigma$, $(G',V')$, which should be what we search.
Is this approach correct? How to make sure that $Th(G)=Th(G')$?
Very similarly in the second case I consider the language of graphs $\mathscr{L}=\{E\}$ and enrich it with a set of $\kappa$ new constants $C=\{c_i|i\in\kappa\}$, and yet anther set of constants $\{v_i\in\kappa\}$
$\Sigma=Th(G)\cup Ax_1(i,j)\cup Ax_2(i,j)\;\;\;$ $i,j\in\kappa$
where $$Ax_1(i,j)=\lnot(c_i=c_j)\wedge\lnot(v_i=v_j)\;\;\;\; Ax_2(i,j)=c_iEv_j$$
Again: is this approach correct? How to make sure that $Th(G)=Th(G')$?
Could we exploit more directly the Lowneheim skolem theorems somehow?
This is the right idea, and I don't think there's any way to deduce this from Löwenheim-Skolem. Since $Th(G)\subset\Sigma$, $G'$ is a model of $Th(G)$. But $Th(G)$ is a complete theory (in just the language of graphs), and so $Th(G')$ (in the language of graphs) cannot be any larger than $Th(G)$, so $Th(G')=Th(G)$.
Note though that your approach in the second case is wrong, since you require $c_i$ to be a neighbor of $v_j$ for all $i$ and $j$. You might not be able to get any model of that in $G$: for instance, $G$ might have two vertices of degree at least $2$, but not two vertices which have the same two neighbors. You instead have to make separate $v_j$'s for each $c_i$.