MaximalIndependentEdgeSet

MaximalIndepndentEdgeSet[g]
gives a maximal independent edge set of an undirected graph g.

whether edges with higher weights are preferred when forming the maximal independent edge set

This defines a small graph:

This shows that the maximal independent edge set contains three edges:

This plots the hexagon with maximal edges highlighted in red:

Needs["GraphUtilities`"]

This defines a small graph:

Out[3]=

This shows that the maximal independent edge set contains three edges:

Out[4]=

This plots the hexagon with maximal edges highlighted in red:

Out[5]=

A matrix representation of a hexagon with a higher weight given to the edge connecting vertices 1 and 6:

This shows that with the default option Weighted->False, the weights are ignored:

This shows that the option Weighted->True, the higher weight edge

is included:

This is a matrix representation of the graph of a torus:

This finds the maximal independent edge set of the torus:

This plots the torus, highlighting members of the maximal independent edge set in red: