MathCastle
Graph TheoryMediumEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Medium problem

A graph has a center vertex 00 joined to four leaves 1,2,3,41,2,3,4 (a star, 44 edges), and nothing else. What is the minimum number of NEW edges that must be added (between any two of the 55 vertices, including a repeat of an existing edge) so that the resulting graph has an Euler circuit?