The University of Montana
Department of Mathematical Sciences

Technical report #27/2009

König-Egerváry graphs are non-Edmonds

P. Mark Kayll
Department of Mathematical Sciences
University of Montana
Missoula MT 59812-0864, USA


König-Egerváry graphs are those whose maximum matchings are equicardinal to their minimum- order coverings by vertices. Edmonds [J. Res. Nat. Bur. Standards Sect. B 69B (1965), 125–130] characterized the perfect matching polytope of a graph G = (V,E) as the set of nonnegative vectors x ∈ RE 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 de Carvalho et al. [J. Combin. Theory Ser. B 92 (2004), 319–324].

Keywords: matching, perfect matching polytope, covering

AMS Subject Classification: Primary 05C70; Secondary 05C35, 90C35, 68R10, 52B99

Download Technical Report: Pdf (96 KB)