A maximum independent edge set of a graph 
is an independent edge
set containing the largest possible number of edges
among all independent edge sets of 
. An independent edge set,
also called a matching, is a subset of the edges
of 
such that no two edges in the subset
share a graph vertex.
A maximum independent edge set, also called a maximum matching, of a graph can be computed in the Wolfram Language
with FindIndependentEdgeSet[g].
The size of a maximum independent edge set is known as the matching
number or edge independence number.
A maximum independent edge set is not equivalent to a maximal independent edge set, which is simply an independent
edge set that cannot be extended to a larger independent
edge set. Every maximum independent edge set is also a maximal
independent edge set, but the converse is not true.
Gallai (1959) showed that, for a graph with no isolated vertices, the size of a minimum edge cover
plus the size of a maximum independent edge set equals the vertex
count.
The blossom algorithm can be used to find a maximum independent edge set in a general graph, while
the simpler Hungarian maximum matching
algorithm can be used for bipartite graphs.
See also
Blossom Algorithm,
Edge Cover,
Hungarian Maximum Matching
Algorithm,
Independence Number,
Independent
Edge Set,
Matching Number,
Maximal
Independent Edge Set,
Maximum Independent
Set Problem,
Maximum Independent
Vertex Set,
Perfect Matching
Explore with Wolfram|Alpha
References
Brualdi, R. A. Introductory Combinatorics, 4th ed. New York: Elsevier, 1997.Cook, W. J.;
Cunningham, W. H.; Pulleyblank, W. R.; and Schrijver, A. Combinatorial
Optimization. New York: Wiley, 1998.Gallai, T. "Über
extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eötvös
Sect. Math. 2, 133-138, 1959.Hopcroft, J. E. and Karp,
R. M. "An 
Algorithm for Maximum Matchings in Bipartite Graphs."
SIAM J. Comput. 2, 225-231, 1973. https://doi.org/10.1137/0202019.Pemmaraju,
S. and Skiena, S. "Maximum Independent Set." §7.5.3 in Computational
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge,
England: Cambridge University Press, p. 318, 2003.Skiena, S. "Maximum
Independent Set." §5.6.3 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 218-219, 1990.Zwick, U. "Lecture Notes
on: Maximum Matching in Bipartite and Non-Bipartite Graphs." https://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf.
2009.Referenced on Wolfram|Alpha
Maximum Independent Edge Set
Cite this as:
Weisstein, Eric W. "Maximum Independent Edge
Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MaximumIndependentEdgeSet.html
Subject classifications
