![]() | 1 | initial version |
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