ABSTRACT
Any graph is completely determined by either its adjacencies or its incidences. This can be restated as: graph adjacencies lead to the adjacency matrices and graph incidences to the incidence matrices, respectively. While the (vertex-)adjacency matrix and its properties have been studied rather thoroughly (e.g., Cvetković et al., 1988, 1995), the (vertex-edge) incidence matrix has been studied less (Rouvray, 1976), although it appears the vertex-edge and edge-cycle incidence matrices were introduced earlier than the adjacency matrix. For example, at the turn of the century, Poincaré (1900) emphasized these matrices when he presented essentially equivalent tableaux appearing in an approach for the construction of geometrical objects (called complexes following Listing (1861)) from elementary units, called cells. In order to describe how the cells t together, Poincaré used the Kirchhoff technique (Kirchhoff, 1847), replacing a system of linear equations by a matrix that he built from his considerations of 0-cells and 1-cells. In present-day terminology the 0-cells and 1-cells are called vertices and edges, which together form a graph. The corresponding matrix is now known as the vertex-edge incidence matrix. Notably, on the strength of this and related papers, Poincaré is regarded as a founder of algebraic topology (Biggs et al., 1976).
