We will count certain connected subgraphs of a "master graph" like a chess board, namely a rectangular grid of size $m\times n$ vertices (rows by columns) with $m\cdot(n-1)$ horizontal and $(m-1)\cdot n$ vertical edges.
All of our graphs will be simple, i.e. the edges are undirected and may be identified by an unordered pair of distinct vertices. Thus there are no "loops" (self-edges from a vertex to itself) nor multiple edges between the same pair of vertices.
More precisely we are counting labelled subgraphs, treating as distinct two subgraphs unless they consist of exactly the same vertices and edges. [If instead we wanted count isomorphic subgraphs only once, we would refer to them as unlabelled subgraphs.]
We make free use of polynomials involving terms like $(m-w)$ and $(n-h)$, but strictly speaking these should be replace by zero if $m \lt w$ or $n \lt h$, as there is no room on the board in those cases for some or all subgraphs. To avoid awkward repetition it will be assumed for the sake of the particular problem here that $m,n \ge 4$, so that all the polynomials are valid without further qualification.
Using the methods outlined below, I created a spreadsheet with $m,n$ as parameters and a row for each (connected) subgraph configuration. The final total number of connected 5-nodes, 4-edge subgraphs on a $9\times 9$ board is $4483$.
A tree is a connected graph with no cycles. This especially relates to the subgraphs we want to count, having four edges and five vertices, because a tree with $k$ vertices always has $k-1$ edges. Conversely, a connected graph with $k$ vertices and $k-1$ edges has no cycles and so is actually a tree.
A particularly nice case to start our counting is a "central" vertex connected to four different "leaf" vertices:
Such a subgraph can be placed on the chess board anywhere that a $2\times 2$ square could be placed, so there are $(m-2)\cdot (n-2)$ of these. It is especially symmetric in that rotations and reflections within the $2\times 2$ square do not generate any additional subgraphs.
We should pause to address an important point: How will we know if all the possible cases are shown and properly counted? For this we need some systematic methods of distinguishing and classifying cases.
A very useful concept for this is a degree sequence which is a descending sequence of nonnegative integers that corresponds to the number of edges incident to the different vertices of a graph. The case described above happens to coincide with subgraphs having a degree sequence $4+1+1+1+1$, since any vertex of degree four in a connected graph of five vertices necessarily takes this form.
The subgraphs of interest here have four edges, and the Handshaking Lemma or degree sum formula tells us that the sum over a corresponding degree sequence will be twice four or eight.
Not every quintuplet of nonnegative integers that sum to eight can be the degree sequence of a graph. For example $5+3+0+0+0$ cannot be realized. But there are efficient algorithms for deciding if a degree sequence is feasible, and in our problem the possible degree sequences can be quickly found.
The other feasible degree sequences are $3+2+1+1+1$ and $2+2+2+1+1$. These two cases involve a number of asymmetric configurations, but they at least provide a way of classifying those configurations.
Degree sequence 3+2+1+1+1
A method of counting subgraphs will now be applied to the case where the maximum degree is $3$, which amounts to the following cases (up to reflection and rotation) having degree sequence $3+2+1+1+1$.
Each of these cases has a minimum "box" or containing frame, within which the subgraph can be reflected. When the box is square (as it is for the final two figures), the subgraph can also be rotated within the box, but if the box is rectangular, then a quarter rotation requires the box to be rotated (or "transposed") as well. In any case we can count all possible ways to place the box in the chess board, and respectively the ways to place the subgraph in the box.
The leftmost figure, a "chair" or "h", just fits into an upright $2\times 1$ box as shown or in quarter rotation a $1\times 2$ transposed box. The upright box can be placed on the chess board in $(m-2)\cdot (n-1)$ locations, while the transposed box goes onto $(m-1)\cdot (n-2)$ locations. Each box allows four distinct reflected/half-rotated versions of the subgraph, so the total number of subgraphs under this specific figure is:
$$ 4(m-2)\cdot (n-1) + 4(m-1)\cdot (n-2) $$
The next figure, very like a capital "F", has the same size boxes and symmetries within those boxes. Thus it gives the same total number of subgraphs as the first figure.
The third figure, perhaps viewed as "y" with a little imagination, fits into a $3\times 1$ box. Thus the upright box has $(m-3)\cdot (n-1)$ board locations, and the transposed box has $(m-1)\cdot (n-3)$ locations. After rotations and reflections, there will be a total number of these subgraphs:
$$ 4(m-3)\cdot (n-1) + 4(m-1)\cdot (n-3) $$
The fourth figure, best called "T" no doubt, fits into a $2\times 2$ square box. It has $(m-2)\cdot (n-2)$ board locations, and because of its bilateral symmetry, four distinct rotations within the square box. The total number of these subgraphs is:
$$ 4(m-2)\cdot (n-2) $$
The fifth possibility is an awkward figure for which I can suggest only "plow" as mnemonic. It fits in a $2\times 2$ square box but has no symmetry, and thus yields a full 8-fold dihedral orbit under rotation/reflection. It thus contributes the following total number of subgraphs:
$$ 8(m-2)\cdot (n-2) $$
Degree sequence 2+2+2+1+1
The remaining cases (no degrees above two) are subgraphs that are simple paths. There are nine such configurations to account for:
By now the procedure for counting each of the congruent copies of these figures should be clear. The minimum bounding box of a figure is found, e.g. a $4\times 0$ box for the first figure, a straight path of length $4$. The rotations and reflections within a box are counted (a divisor of eight) are multiplied by the number of locations for the box. If the box is not square, the corresponding transposed figures and box locations are multiplied and added to the total.
