looking at this graph:
couldn't post a direct link, use:
"i dot imgur dot com slash lqGPaGh.png"
Isn't node "1" a solution for k=1 ? it satisfies both rules: there is a path from 1 to every other node other than "1".
If it's an acceptable answer, then the provided solution does not yield a correct answer for this input.
Am I missing something ?