MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

A graph consists of two separate pieces: a triangle on {1,2,3}\{1,2,3\}, and a star with center 44 and leaves 5,6,75,6,7 (edges 45,46,4745,46,47) — the two pieces share no vertex and no edge. What is the minimum number of new edges (between any two of the 77 vertices) needed so the WHOLE resulting graph is connected and has an Euler circuit?