I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi algorithm to do this, but Havel-Hakimi isn't actually guaranteed to produce connected graphs. Are there any known algorithms to do this?

  • $\begingroup$ Thank you for your comment; you are entirely correct! I somehow completely missed that; I have updated my question accordingly. $\endgroup$
    – Eric J
    Aug 8, 2018 at 22:51
  • 2
    $\begingroup$ Cool. Is this answered by the references/answers at math.stackexchange.com/q/61361/14578 and math.stackexchange.com/q/732303/14578? (Oh, and welcome to CS.SE!) $\endgroup$
    – D.W.
    Aug 8, 2018 at 23:49
  • 1
    $\begingroup$ Does each vertex have a maximum degree fixed ahead of time, or is the exact desired degree known for each vertex? $\endgroup$ Aug 9, 2018 at 2:33
  • $\begingroup$ @StellaBiderman I know the exact desired degree for each vertex. $\endgroup$
    – Eric J
    Aug 9, 2018 at 2:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.