# Find all perfect matchings in a general undirected graph

Is there an algorithm which can compute all perfect matchings of a general undirected graph (assuming they exist)?

• definitely yes. you can iterate all possible solutions over vertices and check if it is a perfect match. Are you looking for efficient one? Why you need all perfect matches? – Mohsen Ghorbani Jul 9 at 16:47
• Is the graph finite? – Yonatan N Jul 9 at 17:35
• Yes. I am looking for an efficient algorithm to find all perfect matchings in general finite undirected graphs, G, of size 100-300 nodes and edges because these correspond to vertex-disjoint cycle covers in a second graph, H, using Tutte's reduction method. The second graph, H, represents a molecular structures and the vertex- disjoint cycle covers correspond to cyclic patterns in the bonding, hence, all the perfect matchings would be needed as they may have physical meaning. – Ganapati Natarajan Jul 10 at 11:38
• It is np-hard for enumerating all PMs in general graphs. you can find the algorithm here – Mohsen Ghorbani Jul 10 at 17:55