Report Number: CS-TR-75-484
Institution: Stanford University, Department of Computer Science
Title: On subgraph number independence in trees.
Author: Graham, Ronald L.
Author: Szemeredi, Endre
Date: March 1975
Abstract: For finite graphs F and G, let $N_F$(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If ${\cal F}$ and ${\cal G}$ are families of graphs, it is natural to ask them whether or not the quantities $N_F$(G), $F \in {\cal F}$, are linearly independent when G is restricted to ${\cal G}$. For example, if ${\cal F}$ = {$K_1$,$K_2$} (where $K_n$ denotes the complete graph on n vertices) and ${\cal G}$ is the family of all (finite) $\underline{trees}$ then of course $N_{K_{1}}$(T) - $N_{K_{2}}$(T) = 1 for all $T \in {\cal G}$. Slightly less trivially, if ${\cal F} = {$S_n$: n = 1,2,3,...} (where $S_n$ denotes the $\underline{star}$ on n edges) and ${\cal G}$ again is the family of all trees then $\sum_{n-1}^{\infty} {(-1)}^{n+1} N_{S_{n}} (T) = 1 for all T \in {\cal G}$. It will be proved that such a linear dependence can $\underline{never}$ occur if ${\cal F}$ is finite, no $F \in {\cal F}$ has an isolated point and ${\cal G}$ contains all trees. This result has important applications in recent work of L. Lovasz and one of the authors.
http://i.stanford.edu/pub/cstr/reports/cs/tr/75/484/CS-TR-75-484.pdf