# Compute perfect matchings in a graph

I am trying to calculate all the perfect matchings of a graph G (i. e., the subgraphs of G such that every two points are connected)

def matchings(G):
"""Returns a list of the perfect matchings of G.
It uses a recursive algorithm. Get a vertex x in G.
Since all the perfect matchings contain exactly one edge for every vertex,
we have that matchings(G) = {<x,y> U matchings(G\{x,y}) for y adjacent to x}.
"""
Ms=[]   #List of mathchings
x = G.random_vertex()
for e in G.edges_incident(x):
H=G.copy()
H.delete_vertices([e,e]
for M in matchings(H):
return Ms


But this gives me

line 14 for M in matchings(H):
SyntaxError: invalid syntax


I don't understand the error (the loop seems fine to me). What's wrong?

edit retag close merge delete

Sort by » oldest newest most voted

I did not check the whole correctedness of your algorithm, but i can see a syntax error at the line

H.delete_vertices([e,e]


At the end of the line, a closing parenthesis is missing.

more

Thank you. Now I use the Jupyter notebook. It's much easier noticing that mistakes with syntax colouring.