PROBLEMS

摘要

Given a graph G =(V; E), a perfect matching M of G is a subset of the set of edges E such that every vertex v 2 V lies on exactly one edge in M. Prove that for each positive integer n there is a planar connected graph G whose total number of perfect matchings is equal to n.