I have the signature $\sigma := \{E\}$ (E is a double symbol relation, which represents if there is an edge between two vertices, e.g. $E_{1,2}$ means there is an edge between vertex 1 and 2).
Now I need to show that the set of all graphs with minimum one perfect matching cannot be defined in first order logic (quantificational logic).
I already showed (just by stating the formal) that when $\sigma = \{E,M\}$ (M is the relation saying if two vertices have a matching), then the set is defined using first order logic.
Any tips on how I can begin my proof? From what I've understood, I should start it by showing that the set of such graphs is infinite, while the set of perfect matchings is finite. But from there I don't know how to use my relation symbol $E$ in that proof.
Long story short: I need to show that if I'm allowed to use only the edges relation, I cannot define graphs with perfect matching.