Number of subgraphs in $P_n$

Question

Fix an integer $n \geq 1$. Suppose that $a_n$ denotes the number of subgraphs in $P_n$. Here $P_n$ denotes the graph with vertices $\{1,2, \dots,n-1, n\}$ and edges $\{j,j+1\}$, for all $1 \leq j \leq n-1$.

Could you please, prove, or give a hint, for the recurrence $$a_n = a_{n-1}+\sum_{0 \leq i \leq n-1}a_i.$$ Here we assume that $a_0 = 1$ (there is 1 empty graph).

Do you know a reference containing this, and similar, results?

Thank you in advance.

Answer 1

It seems to me that it is possible to reason like this. Denote by $G(k)$ the induced subgraph of $P_n$ with vertices $x_k,x_{k+1}\ldots,x_n$. It is clear that $G(k)$ is a simple path. If $H$ is a subgraph of the graph $P_{k}$, then $H+G(k+1)$ is the disjoint union of graphs $H$ and $G(k+1)$.

The set of all subgraphs of graph $P_n$ is the disjunct union of the following sets:

1. $A_0$ is the set of all subgraphs of $P_{n-1}$;
2. $B_k$ is the set of all subgraphs of the form $H+G(k+1)$ where $H$ is a subgraph of $P_k$ and $k=0,1,\ldots,n-1$.

Hence our recurrence formula follows.

Answer 2

I think this is essentially the same idea as @kabenyuk's answer but maybe a little more elementary. You can derive the recurrence by conditioning on node $n$. There are three disjoint cases:

1. Node $n$ does not appear in the subgraph, yielding $a_{n-1}$.
2. Node $n$ appears as an isolated node in the subgraph, yielding $a_{n-1}$.
3. Node $n$ appears in a connected component that is a path starting at node $i$ for some $i<n$, yielding $\sum_{i=1}^{n-1} a_{i-1}=\sum_{i=0}^{n-2} a_i$.

If you want, you can merge the last two cases, thinking of case 2 as a path of length $0$.