MathCastle
Graph TheoryMediumTrees

Trees · Medium problem

A graph has 1010 vertices and these cables: a triangle 12,23,1312, 23, 13; a path 45,56,6745, 56, 67; and another triangle 89,9-10,8-1089, 9\text{-}10, 8\text{-}10. What is the minimum TOTAL number of cables (additions plus removals) needed to turn this graph into a spanning tree of all 1010 vertices?