Labeled graph is a graph with labels defined on edges. Given a labeled graph \(G = (V, E)\) with label set \(L = \{\ell _1, \ell _2, \dots , \ell _q \}\) , a source \(s \in V\) and a sink \(t \in V\) , the Label s-t Cut problem asks to find a minimum size label subset \(L' \subseteq L\) such that the removal of all edges from G with labels in \(L'\) disconnects s and t. This problem is NP-hard. The current best approximation ratio of Label s-t Cut is \(O(\frac{n^{2/3}}{{\text {OPT}}^{1/3}})\) , where \({\text {OPT}}\) is the size of an optimal solution to the problem. This ratio is achieved by a simple purely combinatorial two-phase approximation algorithm. In this paper, we give a new but short (maybe the shortest) proof for the two-phase approximation algorithm. We also perform experiments for the algorithm. Experimental results show that the two-phase approximation algorithm has actually very good practical performance in random graphs.