Questions tagged [matching-theory]
For questions about matchings in graphs.
37
questions
16
votes
4
answers
34k
views
Prove that a $k$-regular bipartite graph has a perfect matching
Prove that a $k$-regular bipartite graph has a perfect matching by using Hall's theorem.
Let $S$ be any subset of the left side of the graph. The only thing I know is the number of things leaving the ...
- 2,031
20
votes
8
answers
48k
views
How to find the number of perfect matchings in complete graphs?
In wikipedia FKT algorithm is given for planar graphs. Not anything for complete graphs. I need to find the number of perfect matchings in complete graph of six vertices.
- 311
8
votes
2
answers
7k
views
Prove that the sum of minimum edge cover and maximum matching is the vertex count
Given a connected graph, how can we prove that the number of edge of its minimum edge cover plus its maximum matching is equal to the number of vertices?
- 115
6
votes
1
answer
2k
views
Maximum "$2$-to-$1$" matching in a bipartite graph
Suppose that we are given a bipartite graph $G$ with bipartition $V(G) = A \mathbin{\dot{\cup}} B$. A $2$-to-$1$ matching in $G$ is a subgraph $M$ such that:
For all vertices $v \in A$, $\deg_{M} v$ ...
- 145k
2
votes
1
answer
901
views
Graph with even vertices and ${n-1}\choose 2$ $+ 1$ edges has a perfect matching
Let G be a simple graph with an even number n of vertices
and suppose that G has at least $n-1\choose 2 $$+ 1$ edges.
Prove that G has a perfect matching.
I tried to use induction but I am ...
- 241
9
votes
1
answer
6k
views
What does 2 to the power x mean in set theory
In a mathematics assignments i encounter the following statement:
We have a finite collection of combinatorial objects $S \subseteq 2^x$ (For example matchings or spanning trees)
What does this ...
- 369
1
vote
1
answer
333
views
Given an arbitrary vertex connectivity $\kappa$, is there a graph that satisfies $\kappa(G) > \alpha'(G)$？
The problem described in the title comes from my previous question:
Find the relationship between vertex connectivity and mathcing number.
I think it is necessary to take it as a new problem.
For ...
- 2,474
1
vote
1
answer
982
views
Perfect Matching on Bipartite Graph
So I was trying to solve this problem
Let $H$ be a bipartite graph with bipartition $A,B$ such that $|A| = |B| = k$. Prove that the graph contains a perfect matching when every vertex has degree of ...
- 510
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
11
votes
2
answers
251
views
Injection from binary strings with $i$ bits to $i+1$ bits
I want to find an injection $F$ from binary strings length $n$ with $i$ bits turned on to $i+1$ bits turned on, with the condition that if $F(S)=S'$, then $S'$ can be obtained from $S$ by simply ...
- 698
9
votes
2
answers
4k
views
Derive Hall's theorem from Tutte's theorem
I'm trying to derive:
Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$
From this:
Tutte Theorem A graph G has a 1-...
- 101
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
5
votes
1
answer
239
views
Looking for name of combinatorial problem- Permute rows and columns to minimize distance to target matrix
I am trying to find a solution (or algorithm) for the following combinatorial problem:
Given an input matrix and a target matrix, find a permutation of the rows and permutation of the columns that ...
- 55
5
votes
1
answer
182
views
How many perfect matchings does a complete k-partite graph have?
Suppose I have a complete k-partite graph $G = K_{n_1, n_2, ..., n_k}$ such that $\sum_{i=1}^k n_i = n$ is even.
How many perfect matchings does $G$ have?
E.g. $K_{1,1,2}$ has 2 perfect matchings; $K_{...
- 71
4
votes
2
answers
799
views
Extending $k$-element subsets of an $n$-element set to $k+1$ element subsets
The question is as follows:
Let $k,n$ be positive integers such that $k < n/2.$ Prove that all $k$-element subsets of an $n$-element set can be extended to all $k+1$ element subsets of the same $...
- 69