The number of linear, directed, rooted, and connected graphs

Introduction. Seifert and Threlfall [20, p. 4] have described the principal problem of topology as zu entscheiden, ob zwei vorgelegte Figuren hom6omorph sind und wo moglich alle Klassen nichthomoomorpher Figuren aufzuzahlen. Our object is to obtain the number of nonisomorphic linear graphs with p points and k lines, and also to count various kinds of generalizations of graphs. These include directed graphs (digraphs), rooted graphs, multiply rooted graphs, and two other generalizations which will be called graphs of strength s and graphs of type t. The fundamental theorem used to secure these results is due to Polya [151 and will be reviewed very briefly in the next section. The author is happy to take this opportunity to thank Professor Polya for kindly permitting the presentation of his unpublished formula for the number of linear graphs in this paper. The form of the solution in every case will be the counting polynomial. Thus gp(x) defined by: p(p-l)/2 gp(X) = j gpkX' k-O where gpk iS the number of graphs with p points and k lines, serves to count all graphs of p points. After counting several generalizations of graphs, we shall derive a formula for the number of connected graphs of any given topological type in terms of the total number of (connected as well as disconnected) graphs of this type. The number of connected graphs in terms of the total number of graphs, which first appeared in Riddell [16] and then in Riddell and Uhlenbeck [18], as well as the number of weakly connected digraphs obtained by Polya (unpublished) will follow as corollaries. A simple variation of the method enables one to count the rooted connected graphs of any given type in terms of the unrooted connected ones and the total number of such graphs. To illustrate the method, the number of forests and rooted forests will be found in terms of the known number of trees. The final section states some unsolved combinatorial problems.