My intuition on this was similar - Pick the highest degree node and connect it to a node of the same degree if available or to one with the next-highest degree, preferring nodes with less connections over those with more. Repeat.

Worked for me so far, and I'm about 6 levels in with the largest node being 8.