  Many graph polynomials, such as the Tutte polynomial, the interlace
polynomial and the matching polynomial, have both a recursive definition and a
defining subset expansion formula. In this paper we present a general,
logic-based framework which gives a precise meaning to recursive definitions of
graph polynomials. We then prove that in this framework every recursive
definition of a graph polynomial can be converted into a subset expansion
formula.
