On the Rank and Nullity of Subgraphs
David P. Brown · SIAM Review · 1966
In Whitney's study [1] of graphs the concepts of rank and nullity were introduced and used to investigate nonseparable and planar graphs. These concepts are fundamental in the area of network theory. Some additional results involving the rank and nullity of graphs are presented below. In particular the relationship between the rank of any graph G and the rank of any subgraph of G is given. A similar relation is given for nullities. Interrelations between the nullity and rank of graphs are established. These results are specializations of known results in matroid theory [2]. If G is any nonnull graph, a subgraph of G, G1, is any subset of the edges of G together with their incident vertices. A proper subgraph of G is a subgraph which contains at least one and not all the edges of G. The complement of a subgraph of G, denoted by 01, is the set of edges of G not contained in G1 and their incident vertices. A graph is separable if it contains a subgraph with one and only one vertex in common with its complement. A component of G is any connected subgraph of G which has no vertices in common with its complement. A tree T of a connected graph G is any connected subgraph containing all the vertices of G and no circuits. If G contains p components Gi , i = 1, 2, * , p, and Ti is a tree of G , then a forest of G is