That's really not a nice behavior :\

the fault seems to be on BlossomV.jl side mlewe/BlossomV.jl#25

Ok, in fact, the problem seems to originate from Blossom V itself, this is so bad :(

// Computes a perfect matching of minimum cost.
// NOTE: a perfect matching of finite cost must exist (otherwise the behaviour is not specified).

We can get around this by adding dummy edges with big weights.