# Find all Independent edge sets in a graph

The function returns only one answer. But most graphs have more than one possible independent edge set.

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 1 <-> 5}]
FindIndependentEdgeSet[g]


Mathematica returns {1 <-> 2, 3 <-> 4}. we know that {1,5} {3,4} is an answer too.

How do we list all possible answers?

Could could find independent vertex sets of the line graph.

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 1 <-> 5}, VertexLabels -> "Name"] lg = LineGraph[g, es = FindIndependentVertexSet[lg, Infinity, All]
(* {{3, 5}, {2, 5}, {2, 4}, {1, 4}, {1, 3}} *)

HighlightGraph[g, EdgeList[g][[#]],
GraphHighlightStyle -> "Thick"] & /@ es Select[Subsets[EdgeList[g], {2, EdgeCount[g]}],
IndependentEdgeSetQ[g, #] &]


{{1 <-> 2, 3 <-> 4}, {1 <-> 2, 4 <-> 5}, {2 <-> 3, 4 <-> 5}, {2 <-> 3, 1 <-> 5}, {3 <-> 4, 1 <-> 5}}

HighlightGraph[g, #] & /@ % Note I cut the subset length off at 2, obviously every individual edge is technically/trivially an independent edge set as well (at least according to IndependentEdgeSetQ )

• very good solution!
– bios
Oct 4 '16 at 8:57