Connected cubic graphs with the maximum number of perfect matchings

Peter Horak, Dongryul Kim

It is proved that for $n\ge 6$, the number of perfect matchings in a simple connected cubic graph on $2n$ vertices is at most $4f_{n-1}$, with $f_n$ being the $n$-th Fibonacci n…