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 1 , S 2 of G , there is a matching from V ( G ) − S 1 ∪ S 2 into S 1 ∩ S 2 . Moreover, the same is true, when instead of two sets S 1 and S 2 we consider an arbitrary König–Egerváry collection. [ABSTRACT FROM AUTHOR]