edge $ij \in E$ with $x$-value $x_{ij} = 1$ (a “1-edge”) belongs to $T$.

\[lem:one-edge\] When $OPT_{LP}(G) = n$ and $|E| > n$, there is a greedy DFS tree $T$ such that all 1-edges are in $T$.

By the assumptions in the lemma, there is some edge $ij
\in E$ that has $x$-value $x_{ij} < 1$. In this case, both vertices $i$ and $j$ can have at most one adjacent 1-edge. Thus, we choose one of these vertices, say $i$, to be the root of the greedy DFS tree. If $i$ is adjacent to a 1-edge, then this 1-edge belongs to the resulting tree by the rules defining the construction of a greedy DFS tree.

Suppose that after we are done constructing the greedy DFS tree, there is a back edge $(i,j)$ that has $x$-value 1. Then when vertex $j$ was traversed in the depth-first search, it should have taken this edge as a tree edge. Otherwise, the edge it did traverse/add to the tree also had an $x$-value of 1, which is a contradiction because a vertex with degree at least three can have at most one adjacent 1-edge, since the $x$-value at each vertex is exactly two, i.e. 