Motivation behind Tutte's 1-factor theorem Hello Everyone,
I am not sure if this question is okay for this site, in case its not feel free to close it.
However, I would love to have it answered. Here goes my question.

A graph $G=(V,E)$ has a perfect matching if and only if for every $U \subseteq V$ the number of connected components with an odd number of vertices in the subgraph induced by $V \backslash U$ is less than or equal to the cardinality of $U$.

I understand the proof given in most texts (eg Diestel's). I have also heard people state that this theorem belongs to the class of theorems where the obvious necessary condition is sufficient. 
What seems strange to me is that I am not able to see why would anyone come up with such a condition? The condition in Hall's theorem looks natural enough to me. But I have not been able to get such a natural feeling for this theorem - as in what would motivate Tutte to come up with such a charaterization for the existence of perfect matchings.
Please let me know if the question is okay for this site (or is just too stupid :( ).
 A: To make the condition seem natural, let's just try to copy Hall's Condition. So what's the first thing we do? We grab some set of vertices. In Hall's Condition this set is often called $X$ and we take it inside one of the partite sets, but we will call it $U$ and choose it arbitrarily since there there isn't any obvious way to restrict its choice in a general graph. 
Then what is the next thing we do in Hall's Condition? We check that $X$ is big enough to take care of all the edges in a perfect matching that must come out of $X$. In Hall's Condition this means we need to check that $X$ has at least as many neighbors as there are vertices in $X$, since no edge of the perfect matching can lie inside $X$. In the general case, the analogous thing to check is that there are at least as many vertices in $U$ as there are odd components of $[V\backslash U]$ because every odd component must send an edge to $U$ in any perfect matching. (You are just trying to guarantee that a large set of edges must come out of $U$ in any perfect matching, and the number of odd components of $[V\backslash U]$ is the only obvious condition that does so. It's really the only thing you can say.) And well now you've stumbled upon Tutte's Condition.
The (sort of) tricky thing then is to realize that the condition is actually sufficient.
A: One way to come up with the characterization is to just run Edmond's matching algorithm (which is pretty natural).  At the end of the algorithm, a matching $M$ and a subset of vertices $U$ has been explicitly constructed that gives equality in the Tutte-Berge formula (which implies Tutte's theorem).  Of course, this is not how history went down since the algorithm came after  the characterization, but in principle it could have.
Also, if you are comfortable with the naturalness of Hall's condition, then it may ease your mind to know that there is a short proof of Tutte's Theorem from Hall's Theorem.  So in some sense, the conditions are not that far apart.  
