Graph Theoretic Results

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.