How could I prove this logical graph problem? 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.
 A: 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.
A: 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.
