How could I prove this logical graph problem?

Question

First of all, I'm not a student yet, and just trying to understand how the higher math stuff works.

Analysis 1-3 and Algebra 1-3 were never a problem so far, but logic tears my mind apart, especially this task here:

Task:

A perfect match in a graph is a subset of its edges, so each node in exactly one of these edges lies.

Let $\sigma := \{E\}$ be a signature in which $E$ is a two-digit relation symbol.

Show or refute: The class of undirected, loop-free graphs with at least a perfect matching is definable in $FO[\sigma]$.

This task makes me crazy since 2 weeks, could you solve this problem? Btw this are no homework, just for me.

Answer 1

This is not FO-definable.

Hint. Consider the two graphs $$G_{2n} : \boxed{1}{-}{-}\boxed{2}{-}{-}\ \dotsm\ {-}{-}\boxed{2n-1}{-}{-}\boxed{2n} \quad \text{and} \quad G_{2n+1}: \boxed{1}{-}{-}\boxed{2}{-}{-}\boxed{3}\ \dotsm\ \boxed{2n}{-}{-}\boxed{2n+1} $$ for $n$ large enough. Then $G_{2n}$ admits a perfect matching, but $G_{2n+1}$ does not. Now, Hanf locality theorem tells you that structures that look locally the same are not distinguished by first-order formulas.

Answer 2

You could look into Ehrenfeucht games. In particular, it is known that a property $\mathcal{P}$ is not FO expressible if there is a sequence of graphs $(G_k,H_k)_{k\in \mathbb{N}}$ such that for all $k$, $G_k$ has property $\mathcal{P}$, $H_k$ does not have property $\mathcal{P}$ and such that Duplicator wins the $k$--round Ehrenfeucht game played on $G_k$ and $H_k$. In particular, it is known that for large $n$, Duplicator wins the $k$--round Ehrenfeucht game played on $C_n$ and $C_{n+1}$. Only one of these has a perfect matching, thus proving what you would like to show.