  Averbouch, Godlin and Makowsky define the edge elimination polynomial of a
graph by a recurrence relation with respect to the deletion, contraction and
extraction of an edge. It generalizes some well-known graph polynomials such as
the chromatic polynomial and the matching polynomial. By introducing two
equivalent graph polynomials, one enumerating subgraphs and the other
enumerating colorings, we show that the edge elimination polynomial of a simple
graph is reconstructible from its polynomial deck and that it encodes the
degree sequence of an arbitrary graph.
