2021/10/18 by Peter Horak, Dongryul Kim · 1 citation
paper · doi:10.1002/jgt.22759
Abstract It is proved that for , the number of perfect matchings in a simple connected cubic graph on vertices is at most , with being the ‐th Fibonacci number. The unique extremal graph is characterized as well. In addition, it is shown that the number of perfect matchings in any cubic graph equals the expected value of a random variable defined on all 2‐colorings of edges of . Finally, an improved lower bound on the maximum number of cycles in a cubic graph is provided.