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

-

It was a typo... I had meant to require G to be connected. Sorry about that. Students who gave a disconnected graph as a counterexample also got full marks.

What you do is this: Every cycle in G has an edge not in M. Delete that edge. Repeat for each cycle. At the end of the process, you end up with a graph with no cycles- i.e. a tree, or a forest if G is disconnected- with a perfect matching induced by M.

-

Assuming that G is connected: Choose your intial subgraph to be (V,M) where M contains only edges from the perfect matching. Now add to G edges until it is connected with no cycles(verify you can do this , it isnt hard) Your final graph is connected with no cycle(hence a tree) and contains perfect matching(thanks to M)

-