the edge with the highest $\x$-value is chosen.

For a given graph $G$ and an optimal solution to $LP(G)$, let $T$ denote a greedy DFS tree with root $r$. We orient $T$ to be an arborescence with root r, and we orient $B(T):= E \setminus{T}$ “backwards", that is, so that each edge in $B(T)$ forms an directed cycle with a path of the tree. This is possible since $T$ is a DFS tree. We use the notation $(i,j)$ to denote an edge directed from $i$ to $j$. Note that once we have fixed a tree $T$, all edges in $E$ can be viewed as directed edges. When we wish to refer to an undirected edge in $E$, we use the notation $ij \in E$. With respect to the greedy DFS tree $T$, we have the following definitions.

An [*internal*]{} node in $T$ is a vertex that is neither the root of $T$ nor a leaf in $T$. We use $T_{int}$ to denote this subset of vertices.

An [*expensive*]{} vertex is a vertex in $T_{int}$ with two incoming edges that belong to $B(T)$. We use $T_{exp}$ to denote this subset of vertices.

As we will see in Lemma \[lem:four\], expensive vertices 