05815687

j

05815687 Mark Kayll, P. K\"onig-Egerv\'ary graphs are non-Edmonds. Graphs Comb. 26, No. 5, 721-726 (2010). 2010 Springer-Verlag, Tokyo EN matching perfect matching polytope covering Zbl 0141.21802 Zbl 1055.05128

doi:10.1007/s00373-010-0940-y

Summary: K\"onig-Egerv\'ary graphs are those whose maximum matchings are equicardinal to their minimum-order coverings by vertices. {\it J. Edmonds} [``Maximum matching and a polyhedron with 0,1-vertices,'' J. Res. Natl. Bur. Stand., Sect. B 69, 125--130 (1965; Zbl 0141.21802)] characterized the perfect matching polytope of a graph $G = (V, E)$ as the set of nonnegative vectors ${{\bold{x}}\in\mathbb R^E}$ satisfying two families of constraints: `vertex saturation' and `blossom'. Graphs for which the latter constraints are implied by the former are termed non-Edmonds. This note presents two proofs-one combinatorial, one algorithmic---of its title's assertion. Neither proof relies on the characterization of non-Edmonds graphs due to {\it M. H. de Carvalho, C. L. Lucchesi} and {\it U. S. R. Murty} [``The perfect matching polytope and solid bricks,'' J. Comb. Theory, Ser. B 92, No.\,2, 319--324 (2004; Zbl 1055.05128)].