Talk:Tutte theorem

The second part of proof of the theorem does not seem complete to me. In particular, why is every connected component of $V\setminus U$ complete? I am willing to believe that this is a consequence of Tutte's Condition and $G^{*}$ being maximal without a matching, but it just isn't clear.

Here is a proof that also covers the case when $V\setminus U$ has components that are not complete. 84.50.78.90 19:16, 8 November 2007 (UTC)

24.208.96.108 17:22, 10 February 2007 (UTC)

I think Tutte's theorem should not have its own article, but should rather be mentioned in an article for the Tutte-Berge formula, of which Tutte's theorem is a special case. The first thing to do regarding this, of course, would be to start an article for the Tutte-Berge formula :) Jamie King 18:05, 13 September 2007 (UTC)

This should remain the main article. The Tutte-Berge formula is a simple consequence of Tutte's theorem via the observation that G has a matching of size k if and only if the graph obtained from G by adding $|V|-2k$ new vertices, each joined to every original vertex of G, has a complete matching. Especially Lime (talk) 14:23, 22 September 2011 (UTC)

Does this theorem work for infinite graphs?

The cardinalities of V and E are not mentioned in the article.

Does this mean that the theorem is valid even if one or both of them are infinite?

Whether this is correct or not, it would be a good idea for the article to discuss the issue of V or E possibly being infinite. 2601:200:C000:1A0:21A7:B740:95E6:BA8D (talk) 18:25, 5 September 2021 (UTC)

I added an infinite version to the article. —David Eppstein (talk) 01:55, 6 September 2021 (UTC)