Two more characterizations of König–Egerváry graphs

Let G be a simple graph with vertex set V(G). A set S⊆V(G) is independent if no two vertices from S are adjacent. The graph G is known to be König–Egerváry if α(G)+μ(G)=|V(G)|, where α(G) denotes the size of a maximum independent set and μ(G) is the cardinality of a maximum matching. A nonempty collection Γ of maximum independent sets is König–Egerváry if |⋃Γ|+|⋂Γ|=2α(G) (Jarden et al., 2015). In this paper, we prove that G is a König–Egerváry graph if and only if for every two maximum independent sets S₁,S₂ of G, there is a matching from V(G)−S₁∪S₂ into S₁∩S₂. Moreover, the same is true, when instead of two sets S₁ and S₂ we consider an arbitrary König–Egerváry collection.