All Questions
Tagged with matching-theory solution-verification
16
questions
0
votes
1
answer
32
views
Understanding proof of Hall's graph theorem
I am struggling with understanding proof of Halls theorem.
Theorem: Let $G=(V_1\cup V_2,E)$ be a bipartite graph and for each $U\subseteq V_1$ let $$N_{G}(U)=\{v\in V_2\ :\ \exists u\in U\text{ such ...
- 115
1
vote
1
answer
41
views
Proof Verification - Lemma on Matchings and M-augmenting paths
Lemma: Let $M$ be a matching and $P$ an $M$-augmenting path. Then, $M'= M \Delta P$ is a matching (with cardinality +1).
I have a proof in my notes but I thought to try proving it myself. My attempt ...
- 67
3
votes
0
answers
122
views
Hall's marriage theorem: sufficiency proof by contraposition
EDIT: New proof (sorry for bumping, but would be nice to have this answered).
I have an alternative proof of Hall's marriage theorem, and would like to know whether it is correct? If yes, how can it ...
- 2,784
3
votes
1
answer
304
views
Hall's Marriage Theorem
I am aware that Hall's Marriage theorem for complete matching goes like "A bipartite graph $G$ with bipartition $(V_1, V_2)$ has a complete matching from $V_1$ to $V_2$ if and only if $$ |N(A)| \...
- 33
1
vote
0
answers
33
views
Expected number of correct answers in a "bijection exercise"
Say you have a language exercise where you have to match $n>2$ words with $n$ images. If you draw $n$ edges uniformly at random step by step (first edge, starting from vertex $1$ goes to image $l_1\...
- 989
2
votes
0
answers
942
views
A tree has at most one perfect matching (proof verification)
Question: Let $T$ be a tree, prove that at most $1$ perfect matching exists in $T$
My Proof:
Let $M$ and $M'$ be perfect matches in the tree $T = (V,E)$
And let $G$ be a graph on the vertex set $V$ ...
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
4
votes
2
answers
4k
views
Hall's theorem for bipartite graphs using König's theorem
Theorem: Let $G=(A\cup B,E)$ be a bipartite graph and for each $S\subseteq A$ let $$N(S)=\{v\in B\ :\ \exists u\in S\text{ such that}\{u,v\}\in E\}$$
Then, $G$ has a matching of size $|A|$ if and only ...
- 2,649
5
votes
1
answer
257
views
Bipartite graph $G=(A,B)$ with $\delta(A)=3n/2$ and no $C_4$ has a matching which saturate each vertex in $A$.
Say $G$ is a bipartite graph with bipartition $(A,B)$ and $G$ is $C_4$-free. Prove that if every vertex in $A$ has degree at least $\frac32 n$ and $|A|\leq n^2$, then $G$ has a matching which uses ...
- 90.7k
1
vote
1
answer
179
views
Minimum Matching Decomposition | proof verification
Let $G$ be a $2k$-regular tripartite graph with $V(G)=X_1\bigcup X_2 \bigcup X_3$, and let $|X_i|=2m+1$ for $i=1,2,3$. What is the minimum number of matchings into which $G$ can be decomposed?
Here ...
user552232
3
votes
1
answer
3k
views
How many different perfect matchings does $K_{n,n}$ have?
How many different perfect matchings does a complete bipartite graph $K_{n,n}$ have?
Here is my reasoning:
Initially, I have $2n$ choices for vertices. Then I can combine one of these vertices with $...
user532588
1
vote
1
answer
916
views
Maximum matching saturating a vertex
Prove or disprove: For every vertex v in a graph G without isolated
vertices, there is some maximum matching that saturates v.
I think this is true: Suppose that vertex $v$ is saturated by some ...
- 1,862
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
21
votes
1
answer
1k
views
Cantor-Bernstein-Schröder Theorem: small proof using Graph Theory, is this correct?
The theorem:
Suppose there exist injective functions $A \to B$ and $B \to A$ between two infinite sets $A$ and $B$. Then there exists a bijection $A \to B$.
Proof:
Let $f: A \to B$ and $g: B \to A$...
- 1,177
6
votes
1
answer
9k
views
Number of perfect matchings in a complete bipartite graph with equal partitions
I have the complete bipartite graph $K_{k,k}$ and I want a formula for the number of perfect matchings in it. I tried to do this by drawing them out to see a trend and came up with $k(k-1)$ which ...
- 105