All Questions
Tagged with matching-theory proof-writing
6
questions
3
votes
1
answer
62
views
Greedy lemma Problem for matching spears to soldiers
The problem has $n$ spears and $n$ soldiers. Spears and soldiers have heights. We want to assign spears to soldiers such that the total height difference of spears and their assigned soldiers is ...
- 307
1
vote
1
answer
248
views
Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. Show that if $ H $ has a perfect matching, then $ G $ has a perfect matching .
Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. We define graph $H$ as follows:
$$ V (H) = {{(V (G) - V (C)) ∪ {c}}}, $$ where $ c $ is a new vertex that we add arbitrarily
$$ E ...
- 141
2
votes
1
answer
845
views
The number of perfect matchings corresponds to the Matrix Permanent
I want to show that the number of perfect matchings in a bipartite graph is precisely the permanent of the adjacency matrix of the graph.
This seems somehow quite natural to me. But how could I give ...
- 4,222
0
votes
2
answers
2k
views
Proving that every connected graph of order 4 that is not $K_{1,3}$ has a perfect matching.
I am asked to prove two things:
(a) Prove that every connected graph of order 4 that is not $K_{1,3}$ has a perfect matching.
(b) Let G be a connected graph of even order. Prove that if G contains ...
- 1,088
1
vote
1
answer
943
views
All stable matchings of a given bipartite graph cover the same vertices.
I believe this proof is pretty obvious, since stable matchings saturate all of the vertices, right?
Still I will give it a go:
Let $M_1$ and $M_2$ be two matchings such that they don't cover the same ...
- 1,862
1
vote
3
answers
2k
views
Stable Marriage / Stable Matching / Gale-Shapley where men rank a subset of women
Given n men and n women, preference rankings for the women, does Gale-Shapley still find a stable matching if the men only rank a subset of women.
From this variation, it's possible that we end up ...
- 370