The purpose of this work is to present a new compact formulation and efficient exact solution algorithm for the Steiner Traveling Salesman Problem (STSP) on an undirected network and its multi-depot extension. The STSP is an uncapacitated node-routing problem looking for a minimum-cost route that visits a known set of customers with service demand, placed at vertices of a given network, which is assumed to be uncomplete. The multi-depot extension, MDSTSP, studies the case when there are several depots and the allocations of customers has to be decided as well. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.