For finite graphs F and G, let NF(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If F and G are families of graphs, it is natural to ask then whether or not the quantities NF(G), F∈F, are linearly independent when G is restricted to G. For example, if F = {K1, K2} (where Kn denotes the complete graph on n vertices) and F is the family of all (finite) trees, then of course NK1(T) − NK2(T) = 1 for all T∈F. Slightly less trivially, if F = {Sn: n = 1, 2, 3,…} (where Sn denotes the star on n edges) and G again is the family of all trees, then Σn=1∞(−1)n+1NSn(T)=1 for all T∈G. It is proved that such a linear dependence can never occur if F is finite, no F∈F has an isolated point, and G contains all trees. This result has important applications in recent work of L. Lovasz and one of the authors (Graham and Lovasz, to appear).
['Ronald L. Graham', 'Endre Szemerédi']
On Subgraph Number Independence in Trees