We consider a graph $G$ of size $d$ with adjacency matrix $A$, whose entries take value in $\{0,1\}$. We are interested in the number of a certain connected subgraph $S$ of size $k$ in $G$. For example, the subgraph $S$ consists of edges $(1,2),(2,3),(3,4),(4,2)$ up to relabeling of the $k = 4$ vertices $1,2,3,4$. We can also view this subgraph as a path of length $k = 4$ from vertex $1$ to vertex $2$. Here we allow repeated vertices in the path, for example, vertex $2$ appears twice.

Question: Is the following claim true?

Let $s$ denote the number of subgraphs $S$ in $G$. It holds that $$ s = \sum_{i = 1}^k\langle \Theta^{(i)}, A^i \rangle, $$ where $\Theta^{(i)} \in R^{d\times d}$ is the coefficient of the $i$-th order polynomial of the adjacency matrix $A$, and $k$ is the size of the subgraph of interest.