A generalization of Tutte's 1-factor theorem to countable graphs (Q800941)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A generalization of Tutte's 1-factor theorem to countable graphs |
scientific article; zbMATH DE number 3878971
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A generalization of Tutte's 1-factor theorem to countable graphs |
scientific article; zbMATH DE number 3878971 |
Statements
A generalization of Tutte's 1-factor theorem to countable graphs (English)
0 references
1984
0 references
\textit{W. T. Tutte's} well-known theorem on 1-factors [Can. J. Math. 6, 347-352 (1954; Zbl 0055.171)] states that a nontrivial finite graph G has a 1-factor (perfect matching) if and only if for every proper subset S of V(G), the number of odd components of \(G-S\) does not exceed \(| S|\). The author presents a characterization of countable graphs possessing perfect matchings that reduces to Tutte's theorem in the finite case. He conjectures that the result is valid for general graphs.
0 references
1-factor
0 references
perfect matchings
0 references
0.9114858
0 references
0.90417606
0 references
0.89753294
0 references
0.8958719
0 references
0 references
0 references
0 references
0.88412327
0 references
