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 :( ).