Find the number of isomorphism classes of connected graphs of $n$ vertices Question
Suppose $g(n)$ is the number of isomophism classes of connected graphs of $n$ vertices such that $\Delta(G) = \mbox{max degree of any vertex of} \ G \leq 3$. Show that there are positive constants $A, c$ such that $f(n) \geq Ae^{cn}$ for every $n$.
Ideas
My only thought is proof by induction. Somehow show that if the result is true for $k$, then we want to show that $f(n+1) \geq e^c f(n)$ for any $n$, and since we have a freedom of choice for $c$, we could even just show that there are twice as many as $n$ increases by 1.
Freedom to chose $A$ makes the base case(s) of $n=1( 2)$ rather easy too.
Would this work? I feel as if I have over simplified it. How would one even proving the inductive step?
 A: You're being asked to show a rather weak bound, so over-simplifying is your friend. In fact, I think you haven't simplified the problem enough. Having $f(n)$ double when you increase $n$ by $1$ is still asking for a lot.
Instead, just try to find a family of graphs (connected ones, with maximum degree $3$) on an arbitrary number of vertices where you can make exponentially many choices: for example, having $n$ places in a $kn$-vertex graph where you can make a choice with $2$ options would mean $f(kn) \ge 2^n$, which almost entirely proves the bound you want.
Here is just one example. It's probably not the simplest one, and I encourage you to come up with your own.

Here, the dashed edges can be included or excluded, giving us $16$ different graphs on $19$ vertices with maximum degree $3$. We can make the chain of $4$-cycles with a dashed edge cutting them in half arbitrarily long.
Obviously, not all connected graphs $G$ with $\Delta(G) \le 3$ look like this (in fact, almost none of them do) but if the number of graphs that do have this structure is exponential, that's a lower bound on $f(n)$ already.
If you do this, there's still a few things left to check:


*

*We need to know that two of these graphs are only isomorphic when you've made the same sequence of choices. (That's the reason there's a $3$-cycle on the left end of the graph above.)

*It's obvious that we can extend this construction to any number of vertices $n$ of the form $4k+3.$ But we need the construction to work for all $n$, so we need to do something that "uses up" between $0$ and $3$ extra vertices.

*Then we need to convert the vague idea that the number of graphs we get this way is exponential in $n$ into a bound of the form $f(n) \ge Ae^{cn}$.

