Independence numbers of graphs-an extension of the Koenig-Egervary theorem

Let G be an arbitrary finite, undirected graph with no loops nor multiple edges. In this paper the inequality β₀?n ? β₁ is investigated where β₀ is the independence number of G, n is the number of vertices, and β₁ is the cardinality of a maximum edge matching. The class of graphs for which equality holds is characterized. A polynomially-bounded algorithm is given which tests an arbitrary graph G for equality, and computes a maximum independent set of vertices when equality holds. Equality is “prevented” by the existence of a blossom-pair-a subgraph generated by a certain subset m_i of edges from a maximum edge matching M for G. It is shown that β₀ = n ?β₁?|R| where R is a minimum set oof representatives of the family {m_i} of blossom pair-generating subsets of M. Finally, apolynomially-bonded algorithm is given which partitions an arbitrary graph G into subgraphs G₀, G₁,…, G_q such that $\text{β}{}_0\text{(G) =}\text{∑}\text{i=0}\text{q}\text{β}{}_0\text{(G}{}_{\mathrm{i}}\text{)}$. Moreover, if arbitrary maximum independent subsets of vertices S₁, S₂,…, S_q are known, then a polynomially-bounded algorithm computes a maximum independent set S₀ for G₀ such that S=∪{S_i; i=0, 1,hellip;,q} is a maximum independent subset for G.