  We look for graph polynomials which satisfy recurrence relations on three
kinds of edge elimination: edge deletion, edge contraction and deletion of
edges together with their end points. Like in the case of deletion and
contraction only (W. Tutte, 1954), it turns out that there is a most general
polynomial satisfying such recurrence relations, which we call $\xi(G,x,y,z)$.
We show that the new polynomial simultaneously generalizes the Tutte
polynomial, the matching polynomial, and the recent generalization of the
chromatic polynomial proposed by K.Dohmen, A.P\"{o}nitz and P.Tittman (2003),
including also the independent set polynomial of I. Gutman and F. Harary,
(1983) and the vertex-cover polynomial of F,M. Dong, M.D. Hendy, K.T. Teo and
C.H.C. Little (2002). We establish two definitions of the new polynomial:
first, the most general confluent recursive definition, and then an explicit
one, using a set expansion formula, and prove their identity. We further expand
this result to edge-labeled graphs as was done for the Tutte polynomial by T.
Zaslavsky (1992) and B. Bollob\'as and O. Riordan (1999). The edge labeled
polynomial $\xi_{lab}(G,x,y,z, \bar{t})$ also generalizes the chain polynomial
of R.C. Read and E.G. Whitehead Jr. (1999). Finally, we discuss the complexity
of computing $\xi(G,x,y,z)$.
