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: 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.
A: 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.
A: 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)
