直接容斥成度数 $\lt 2$ 的点集看起来不是很有前途，比较难优于 $O(3^n)$。考虑类似数点双连通子图那样一个点一个点做。令 $f_{i,S}$ 表示编号 $\leq i$ 的点都满足度数 $\geq 2$，考虑从 $f_{i-1}$ 推出 $f_{i}$。容易发现 $f_{i,S}$ 就是 $f_{i-1,S}$ 减掉其中 $i$ 的度数为 $0$ 和 $1$ 的。

$i$ 的度数为 $0$ 的非常好算，就是 $f_{i-1,S\setminus \{i\}}$。

$i$ 的度数为 $1$ 时，设 $i$ 连向的点是 $j$。如果 $j\lt i$ 或者 $j$ 的度数 $\geq 3$，那么把这条边删去之后就相当于 $f_{i-1,S\setminus \{i\}}$。否则相当于删掉 $(i,j)$ 之后 $j$ 的度数变成了 $1$，然后接着找到 $j$ 连向的那个 $k$，判断 $k$ 是否满足 $k\lt i$ 或者度数 $\geq 3$，然后一路沿着这条链传递下去直到找到一个编号 $\lt i$ 或者度数 $\geq 3$ 的点停下来。然后假设链上的点集是 $T$，那么最后就是 $f_{i-1,S\setminus T}$ 再乘上 $T$ 中选一条 $i$ 为端点的链的方案数。对每个 $T$ 先算成为链的方案数再做子集卷积显然太蠢了，考虑把这条链倒过来，从 $S\setminus T$ 作为起点最后走到 $i$ 就可以直接 dp 了。

于是就做完了，总复杂度 $O(2^nn^3)$。