Theorem 1. Let
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