On (3,1)-regular graphs with one more vertex than edges

Sequence A339987 of the OEIS counts (3,1)-regular graphs having one more vertex than edges by half the number of vertices.

A recurrence relation satisfied by this sequence was guessed by Kauers and Koutschan in 2023.

We confirm it in three ways: first, by a representation as the diagonal of a triple sum and an elaborate variant of traditional creative telescoping that makes an a posteriori validation possible; second, by a residue representation and a direct calculation by reduction-based creative telescoping; third, by a combinatorial recurrence on graph families and a calculation by differential elimination.

Each of those three approaches leads to a formally complete proof and involves a computer calculation in one way or another.