Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every node has a degree at most 3, which would correspond to a parent and two children?

  • $\begingroup$ Would you accept a counterexample as an answer? $\endgroup$
    – John L.
    Nov 29, 2019 at 22:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.