אלגוריתם:

• מצא עפ"מ $T$
• צבע את כל שאר הקשתות בצהוב
• מצא עפ"מ צהוב ביותר $T'$
• החזר של-$G$ יש עפ"מ יחיד אמ"מ $T'$ לא מכיל קשת צהובה

נכונות: אם ל-$G$ יש יותר מעפ"מ אחד אז יש לו עפ"מ שונה מ-$T$ ולכן קיים עפ"מ עם קשת צהובה אחת לפחות. מצד שני אם ל-$G$ קיים רק עפ"מ אחד אז $T' = T$ולכן אין ב-$T'$ אף קשת צהובה.

סיבוכיות: מציאת עפ"מ $\times$ 2 + צביעה של הקשתות - $O(|E|\log|V|)$.