0
$\begingroup$

It seems that the maximum matching number decreases when some independent (not connected) vertices collapse into one vertex, but I don't know if it is absolutely true. Would maximum matching number increases when two vertices are connected to form a new edge?

Any proof? Thanks! enter image description here Definitions: Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

A maximum matching (also known as maximum-cardinality matching1) is a matching that contains the largest possible number of edges.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Try to find a proof that it can't happen! Keep trying. Hint:

Suppose you have a maximum matching for the collapsed graph. Can you use that to find a matching for the original graph? How many edges does it have? What does that imply about your question?

If you're really stuck, try to write a program to enumerate all graphs with at most 6 vertices (say) and see if the matching number can ever increase after collapsing an edge. That should enable you to form a reasonable conjecture, which you can then try to prove, or should give you a counterexample.

Improve this answer
$\endgroup$
0
1
$\begingroup$

I just find the proof in Karp, Richard M., and Michael Sipser. "Maximum matching in sparse random graphs." Foundations of Computer Science, 1981. SFCS'81. 22nd Annual Symposium on. IEEE, 1981.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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