Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
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". –  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
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. –  Austin Mohr Nov 14 '11 at 18:56
add comment

2 Answers 2

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.