Если подграф является линейным графом и максимальная стоимость ребра из этого графа равна стоимости ребра, замыкающего обход, то есть соединяющего концы линейного графа, то этот замкнутый обход будет оптимальным обходом первоначальной - задачи.
Доказательство очевидно из линейности
и предыдущих рассуждений.