Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
A graph consists of two separate pieces: a triangle on , and a star with center and leaves (edges ) — the two pieces share no vertex and no edge. What is the minimum number of new edges (between any two of the vertices) needed so the WHOLE resulting graph is connected and has an Euler circuit?