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