WOLFRAM

Wolfram Language & System Documentation Center

IndependentEdgeSetQ[g,elist]

yields True if the edge list elist is an independent edge set of the graph g, and False otherwise.

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
See Also
Related Guides
History
Cite this Page

IndependentEdgeSetQ

IndependentEdgeSetQ[g,elist]

yields True if the edge list elist is an independent edge set of the graph g, and False otherwise.

Details

  • An independent edge set is also known as a matching.
  • An independent edge set is a set of edges that are never incident to the same vertex.
  • IndependentEdgeSetQ works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples  (1)

Test whether a set of edges is an independent edge set:

Wolfram Language code: IndependentEdgeSetQ[[image], {12, 45}]

Scope  (5)

Test undirected graphs:

Wolfram Language code: IndependentEdgeSetQ[[image], {12, 36, 45}]

Directed graphs:

Wolfram Language code: IndependentEdgeSetQ[[image], {21, 36, 54}]

Multigraphs:

Wolfram Language code: IndependentEdgeSetQ[[image], {12, 36, 45}]

Mixed graphs:

Wolfram Language code: IndependentEdgeSetQ[[image], {21, 36, 54}]

IndependentEdgeSetQ works with large graphs:

Wolfram Language code: g = GridGraph[{10, 10, 10, 10}];
Wolfram Language code: IndependentEdgeSetQ[g, {12, 56}]//Timing

Applications  (2)

Enumerate all independent edge sets for a cycle graph:

Wolfram Language code: g = CycleGraph[4]

Enumerate all subsets of edges and select the independent edge sets:

Wolfram Language code: Subsets[EdgeList[g]]
Wolfram Language code: esl = Select[%, IndependentEdgeSetQ[g, #]&]

Highlight independent sets:

Wolfram Language code: Table[HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], {h, esl}]

Enumerate all maximal independent edge sets for a wheel graph:

Wolfram Language code: g = WheelGraph[5]

Find the length of a maximal independent edge set:

Wolfram Language code: Length[FindIndependentEdgeSet[g]]

Enumerate all edge subsets of length 2 and select the independent edge sets:

Wolfram Language code: esl = Select[Subsets[EdgeList[g], {2}], IndependentEdgeSetQ[g, #]&]

Highlight maximal independent sets:

Wolfram Language code: Table[HighlightGraph[g, h, GraphHighlightStyle -> "Thick"], {h, esl}]

Properties & Relations  (3)

A largest independent edge set can be found using FindIndependentEdgeSet:

Wolfram Language code: PetersenGraph[5, 2]
Wolfram Language code: IndependentEdgeSetQ[%, FindIndependentEdgeSet[%]]

Bipartite graphs have independent edge sets and vertex covers of equal length:

Wolfram Language code: g = CompleteGraph[{2, 3}]
Wolfram Language code: Length[FindVertexCover[g]] == Length[FindIndependentEdgeSet[g]]

For a graph without isolated vertices, the sum of the size of the independent edge set and the size of the edge cover equals the number of vertices:

Wolfram Language code: g = PetersenGraph[5, 2]
Wolfram Language code: Length[FindEdgeCover[g]] + Length[FindIndependentEdgeSet[g]] == VertexCount[g]
Wolfram Research (2010), IndependentEdgeSetQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html (updated 2014).

Text

Wolfram Research (2010), IndependentEdgeSetQ, Wolfram Language function, https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html (updated 2014).

CMS

Wolfram Language. 2010. "IndependentEdgeSetQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html.

APA

Wolfram Language. (2010). IndependentEdgeSetQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html

BibTeX

@misc{reference.wolfram_2026_independentedgesetq, author="Wolfram Research", title="{IndependentEdgeSetQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html}", note=[Accessed: 12-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_independentedgesetq, organization={Wolfram Research}, title={IndependentEdgeSetQ}, year={2014}, url={https://reference.wolfram.com/language/ref/IndependentEdgeSetQ.html}, note=[Accessed: 12-June-2026]}