COUNTING PERFECT MATCHINGS

Abstract. Let G be a graph on n vertices. A perfect matching of the vertices of G is a collection of n/2 edges whose union is the entire graph. This definition only applies to graphs with an even number of vertices, however. We present a generalization of the notion of a perfect matching to include graphs with an odd number of vertices. Then we convince a skeptical reader of its relevance by producing a recurrence that counts perfect matchings, relying heavily o