Testing whether an undirected simple graph G contains an eulerian subgraph spanning all its nodes is \(\textrm{NP}\) -complete, by observing that supereulerian testing is exactly hamiltonian testing for 3-regular graphs. A restatement of this problem is finding a matching among the nodes in G of odd degrees and joining the matched nodes with (edge-disjoint) paths, ensuring that the removal of the edges in these paths does not disconnect G. This formulation has two extreme cases: (1) when all nodes in G have odd degrees, and (2) when only two nodes in G have odd degrees. The class of graphs in the former case contains all 3-regular graphs, so it is NP-complete. The class of graphs in the latter case is exactly all semi-eulerian graphs, and the complexity of the problem was unknown. We prove that supereulerian testing is \(\textrm{NP}\) -complete even for semi-eulerian graphs. This implies that, for each integer \(k \ge 1\) , supereulerian testing on graphs with exactly k pairs of odd-degree nodes is NP-complete. Then, we devise efficient exact algorithms for \(k = 1\) . Our algorithm is based on finding a novel sparse certificate for supereulerian testing that can be efficiently computed. Our sparse certificate is triangle-free and has arboricity at most 2. In contrast, Catlin’s sparse certificate for supereulerian testing also satisfies the two properties, but it has no known efficient algorithm to compute. Our algorithm has runtime \(O(1.362^n)\) for n-node semi-eulerian graphs. This algorithm complements the existing two algorithms for hamiltonian testing (i.e. supereulerian testing) on n-node 3-regular graphs with runtimes \(O(1.251^n)\) and \(O(1.260^n)\) respectively.