# How to find the graphs having exactly one perfect matching from the following collection?

Anonymous

.

for g in graphs.nauty_geng('8 -c'):
if g.size()==10:
k=A.determinant()
show(k)
g.show()


Here I am trying to obtain those graphs which have a unique perfect matching, that is, those graphs which have exactly one perfect matching.

edit retag close merge delete

Check again the definition of perfect matching https://en.wikipedia.org/wiki/Perfect.... For graphs of order 7, the answer is obvious from the definition: none.

( 2022-07-04 09:02:00 +0200 )edit

You are correct. I have edited my code now..Can we find now?

( 2022-07-04 09:04:46 +0200 )edit

You can use method perfect_matchings and discard graphs with more than 1 perfect matching.

( 2022-07-04 17:41:03 +0200 )edit

It'd be more efficient to request specific number of edges from nauty: '8 10:10 -c' rather than checking if g.size()==10:

( 2022-07-06 13:45:24 +0200 )edit
( 2023-01-10 20:59:04 +0200 )edit

Sort by ยป oldest newest most voted

By a theorem of Berge, if a graph G with a perfect matching M contains an alternating cycle, then the perfect matching is not unique. Several algorithms to check uniqueness of a perfect matching have been proposed. See for instance the algorithm by Gabow, Kaplan and Tarjan https://doi.org/10.1006/jagm.2001.1167

A more brute force approach, based on methods already available in Sagemath, is the following:

def has_unique_perfect_matching(g):
j = 0
for _ in g.perfect_matchings():
j += 1
if j == 2:
# more than one perfect matching
break
return j == 1

def graphs_with_unique_perfect_matching(n):
i = 0
for g in graphs.nauty_geng('{} -c'.format(n)):
if has_unique_perfect_matching(g):
i += 1
print(i, g.graph6_string())


You get:

sage: graphs_with_unique_perfect_matching(5)
sage: graphs_with_unique_perfect_matching(6)
1 ECR_
2 ECRo
3 ECRw
4 ECr_
5 ECpo
6 ECqg
7 ECro
8 ECrg
9 ECrw
10 ECZ?
11 ECZO
12 ECZG
13 ECZW
14 ECzW
15 ECvo
16 ECuw
17 ECvw
18 EEiW
19 EEhW
20 EQjO
sage: graphs_with_unique_perfect_matching(7)
sage: graphs_with_unique_perfect_matching(8)
1 G?@F_
2 G?@Fo
3 G?@Fw
4 G?@F{
5 G?DE_
...
654 GCQRVO
655 GCQRUS
656 GCQRVS
`
more