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 🙁 ).
Best Answer
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.