Revision history [back]

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