We base on the official editorial and obtain a slightly better time complexity, some technical details will not be repeated.

Consider the graph has “generalized edge” \(e\) with two weights \((a_e, b_e)\), means that for a coloring \(C\colon V\to [k]\), the contribution of the edge \(e\) is \(a_e\) if \(C(u)=C(v)\), and \(b_e\) if \(C(u)\neq C(v)\).

We have two kinds of strategies to make the graph smaller:

1. If a graph has a leaf node \(v\), i.e., \(\deg v = 1\), we can simply remove the node and obtain the graph \(G'\), the answer of the original graph is \(a_e + (K-1)b_e\) multiplied by the answer of \(G'\). Similarly, if there is a node with \(\deg v = 2\), we can contract that node and replace it with a generalized edge.

2. We try to use Deletion–contraction formula when there are two adjacent nodes with \(\deg = 3\). Note that in the graph \(G/ e\) there are \(m-1\) edges, and for the graph \(G \setminus e\), we will immediately have two contractions, so the graph will have \(m-3\) edges.

If both strategies cannot be applied, then the graph satisfies \(\deg v \geq 3\) for each \(v\), and \(\deg u + \deg v \geq 7\) for each \((u, v)\in G\). By double counting, we can see that \(n \leq \frac{7}{12} m\). We can use set power series to compute the answer.

The time complexity of such recursion can be bounded by \(T(m)=T(m-1)+T(m-3)+O(2^{\frac 7{12}m}m^2)\), the \(O(2^{\frac 7{12}m}m^2)\) term dominates. So this algorithm has time \(O(1.499^m m^2)\).

I think a smaller exponent is possible by considering a smarter recursion strategy and a careful analysis.