5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ I changed the question's title to better correspond to its content. You don't appear to be interested in the historical development of the theorem, but rather the motivation behind this characterization. Perhaps a better way to phrase the question would be to ask, is there any algorithmic or theoretical advantage to this (rather daunting) condition. $\endgroup$
    – Alon Amit
    Commented Apr 10, 2011 at 4:12
  • $\begingroup$ @Alon, yes thats a more appropriate title. The reason I asked about "history version" is that I am not specifically looking for an algorithmic advantage. I do not know how can I best put it; but what I really want is to look inside Tutte's mind and better understand the reason why would one come up with such a characterization, which to me, does not sound very natural. Of course, the "motivation version" is probably still much better. Thanks for that change. $\endgroup$
    – Itachi Uchiha
    Commented Apr 10, 2011 at 4:30

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ this is certainly helpful. thanks, i think i need to increase my comfort with existing literature. sorry for not having upvoted your answer - truth is i could not - for the lack of reputation points $\endgroup$
    – Itachi Uchiha
    Commented Apr 10, 2011 at 12:29
8
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for your reply Oliver. While I certainly see what you mean, I guess probably I did not do a good job asking what I wanted to know. I am aware of one proof of this theorem is due to Hetyei and Lovasz. While going through that proof I felt that this proof was certainly an afterthought (of course, as the theorem is due to Tutte). It looked like there was some air of mystery about it and therefore I was also curious to know Tutte's original proof. Maybe I am still doing a pretty bad job of explaining what I want to know. In case, its not clear, please let me know. $\endgroup$
    – Itachi Uchiha
    Commented Apr 10, 2011 at 11:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .