¿Un gráfico siempre tiene un árbol de expansión mínimo que es binario?

Tengo un gráfico y necesito encontrar un árbol de expansión mínimo para un gráfico dado. ¿Qué se debe hacer para que la salida obtenida sea un árbol binario?

No hay nada que hacer: por ejemplo, dejar $S_k$denotar el gráfico de estrella con$k$hojas. La gráfica$S_k$ tiene un árbol de expansión único (que es $S_k$ en sí), y tiene un vértice con grado exactamente $k$.

De hecho, el problema general de encontrar un árbol de expansión mínimo con restricción de grado es NP-completo.