Добудуємо до деякого мінімального остовного дерева, позначимо його. Якщо ребро, то лема доведена, тому розглянемо випадок, коли ребро. Розглянемо шлях в від вершини до вершини. Так як ці вершини належать різним часткам розрізу, то хоча б одне ребро шляху перетинає розріз, назвемо його. За умовою леми. Замінимо ребро в на ребро. Отримане дерево також є мінімальним остовне деревом графа, оскільки всі вершини і раніше пов'язані і вага дерева не збільшився. Отже можна доповнити до мінімального остовного дерева в графі, тобто ребро - безпечне.