Consider the number of leaf-free subgraphs of the $2 \times n$ grid—which is to say, the number of ways to draw lines on the $2 \times n$ grid such that no grid point has degree exactly 1.
For example, when $n = 4$ there are $15$ such subgraphs:
The number of leaf-free subgraphs of the $2 \times n$ grid is given by the linear recurrence
$a(1) = 1$
$a(2) = 2$
$a(n+1) = 5\left(a(n) - a(n-1)\right)$.
What is a combinatorial explanation for this recurrence?
I posted this question on Reddit, and user bairedota posted a response that effectively solved the problem.
The idea: We start with a subset of generation $n$ and we build to generation $n+1$.
First, remove all subgraphs that do not have a vertical edge at the rightmost position. There are $a(n) - a(n-1)$ such graphs, because we subtract out those in the previous generation that are extended by a "blank":
To each of these, we construct five children. Three "generic" children, and two children that depend on the shape of the parent.
i) Extend by a blank:
ii) Extend by a full square:
iii) Extend by a square as above, but delete the vertical edge:
iv) Special case 1:
v) Special case 2:
Since this creates $5(a(n) - a(n-1))$ distinct leaf-free figures, this enumerates all possible leaf-free subgraphs of the $2 \times (n+1)$ grid.