Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'd like to use FindIndependentEdgeSet[g] repeatedly to get random maximal matchings of a fixed graph, but each time I call this function it gives me the same answer (i.e. the same list of edges).

How do I "randomise" it?

share|improve this question
@Öskå Select[Subsets[EdgeList[g = CycleGraph[4]]], IndependentEdgeSetQ[g, #] && Length@# == 2 &] – Dr. belisarius May 23 '14 at 0:00
@belisarius R-r-r-ight :) Deleting comments so I don't look stupid :P – Öskå May 23 '14 at 9:08

Example graph:

g = PetersenGraph[5, 5];

Get independent edge sets:

indies = Select[Subsets[EdgeList[g]], IndependentEdgeSetQ[g, #] &];

Get some random set (repeat as needed):


(* {1<->1, 2<->2, 3<->3, 4<->9, 6<->7} *)

Edit: Rahul notes I missed the "maximal" part.

(* pull out only longest sets *)
With[{ml = Max[Length /@ indies]}, indiesM = Select[indies, Length[#] == ml &]];

(* repeat as needed *)
share|improve this answer
This does not always give maximal matchings. So it solves the problem in the title of the question but not the one in the body... – Rahul May 23 '14 at 4:16
@RahulNarain: Thanks for catching, edited. – ciao May 23 '14 at 6:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.