A Characterization of König–Egerváry Graphs Using a Common Property of All Maximum Matchings

The independence number of a graph G, denoted by α ( G ) , is the cardinality of an independent set of maximum size in G, while μ ( G ) is the size of a maximum matching in G, i.e., its matching number. G is a König–Egerváry graph if its order equals α ( G ) + μ ( G ) . In this paper we give a new characterization of König–Egerváry graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a König–Egerváry graph.