3
$\begingroup$

True or false: If G has a perfect matching then G has a spanning tree that also has a perfect matching.

I've tried finding all possible graphs with perfect matchings I can find to try this but I've yet to find a counterexample and the constant failure to do so has led me to believe otherwise. I want to tell myself this is true but I'm not quite sure how to go about that.

I've thought of using examples to help me derive a proof, but it seems rather too iterative. Given any G with perfect matching we start removing non-covered edges besides the ones connecting edges together. From that point if there exists a cycle we can simply remove an non-covered edge once more to form a spanning tree of G. this does not seem reliable for all graphs however..

  • 1
    A graph with a perfect matching need not have a spanning tree at all.2011-11-14
  • 0
    Interesting. Guess I'll try more counter examples2011-11-14
  • 1
    Suppose your graph is just two disjoint edges. It has a perfect matching, but no spanning tree. To rule out this pathology, you can revise your question by saying either 1) $G$ is connected or 2) replace "spanning tree" with "spanning forest".2011-11-14
  • 0
    No, this is word for word. I just assumed that G has to be connected since it else it would be rather trivial like you've shown. Looks like I over assumed things here! Thanks.2011-11-14
  • 2
    @Room You may want to double-check that your professor/text doesn't make a grand declaration that all graphs are assumed to be connected unless otherwise stated. This is a somewhat common convention.2011-11-14

3 Answers 3