Submitted: June 29, 2004\
    Mathematics Subject Classifications: 05C50, 05C60
title: 'Kocay’s lemma, Whitney’s theorem, and some polynomial invariant reconstruction problems'
---

Introduction {#sec-intro}
============

Suppose we are given the collection of induced subgraphs of a graph. There is a natural partial order on this collection defined by the induced subgraph relationship between members of the collection. An incidence matrix may be constructed to represent this relationship along with the multiplicities with which members of the collection appear as induced subgraphs of other members. Given such a matrix, is it possible to construct the graph or compute some of its invariants? Such a question is motivated by the treatment of chromatic polynomials in Biggs [@biggs1993]. Biggs demonstrates that it is possible to compute the chromatic polynomial of a graph from its incidence matrix. The idea of Kocay’s lemma in graph reconstruction theory is extremely useful in studying the question for other invariants. In this paper, we present several results on a relationship between Ulam’s reconstruction conjecture and the incidence matrix. Extending the reconstruction results of Tutte and Kocay, we show that many graph invariants can be computed from the incidence matrix. We then consider the problem of computing the characteristic polynomial 