# Different formulation of a Traveling Salesman Problem

Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions:

• for each $v \in V$ there exactly two distinct edges in $E'$ which are adjacent to $v$
• $v_0$ is reachable from each $v \in V$ with edges in $E'$

I'm interested if this is a formulation of the Traveling Salesman Problem or if this is weaker. It occurs in an exercise I do as exam preperation. The task is to encode it as a linear integer program.

-

By 1st condition the subgraph on $E'$ is a (disjoint) union of cycles. By 2nd condition it is just one cycle. So this problem is equvivalent to Traveling Salesman Problem.