*Theorem 1. Let G be an acyclic,
undirected graph with v vertices and
e edges.
If there are at most n edges incident on a vertex, then there are
at most 1 + 2e + n(e-1)/2 connected subgraphs having
at most 3 vertices.*

To prove this, one first reduces to the connected case,
in which case *e=v-1*.
There are clearly *2e+1* connected subgraphs having at most 2 vertices,
so the problem is to bound the number of connected subgraphs having
exactly 3 vertices. One can show that this number is maximized when
all the vertices of *G*
have either valence 1 or valence *n* (or as close
to this as possible). There will be at most *(e-1)/(n-1)*
vertices with valence *n*, and each of these defines
connected subgraphs having 3 vertices.

Allowing substitutions means that some of the vertices have *variants*
that are distinguishable from the original vertex.
Subgraphs are allowed to have at most one variant vertex.
The following is an easy calculation given the one in the
theorem above:

*Corollary 2. Let G be an acyclic, undirected graph with
v vertices and e edges.
If there are at most n edges indident on a vertex, and if each
vertex has at most m variants, there there are at most
1 + M + (3m + 2)e + (3m+1)n(e-1)/2 connected subgraphs having
at most 3 vertices, where at most one of the vertices is a variant.*

Fri Jan 20 22:04:00 EST 1995