# Graph Theory - Perfect Matchings

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..

-
A graph with a perfect matching need not have a spanning tree at all. –  Chris Eagle Nov 14 '11 at 18:30
Interesting. Guess I'll try more counter examples –  Room Nov 14 '11 at 18:35
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". –  Austin Mohr Nov 14 '11 at 18:49
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. –  Room Nov 14 '11 at 18:52
@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. –  Austin Mohr Nov 14 '11 at 18:56

Assume that $G$ is connected and has a perfect matching $M$. Weight the edges of $G$ by assigning weight $1$ to each edge in $M$ and weight $2$ to each edge not in $M$. Now apply Kruskal’s algorithm to find a minimal weight spanning tree $T$ for $G$. Kruskal’s algorithm will automatically include in $T$ all of the edges of $M$, so $M$ will be a perfect matching for $T$ as well.

As others have noted, if $G$ is not connected, it can’t have a spanning tree at all, and the assertion is trivially false.

-