MathCastle
Graph TheoryMediumEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Medium problem

A tree has a path 1-2-3-4-51\text{-}2\text{-}3\text{-}4\text{-}5 (edges 12,23,34,4512,23,34,45) with an extra leaf 66 attached to vertex 22 and another extra leaf 77 attached to vertex 44 (edges 26,4726, 47). What is the minimum number of new edges that must be added so the resulting graph has an Euler circuit?