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

  • 2
    @Roo$m$ You may wa$n$t to double-check that your professor/te$x$t 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

1

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.

1

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.

1

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)