Questions tagged [matching-theory]
For questions about matchings in graphs.
567
questions
1
vote
2
answers
2k
views
Perfect matching in bipartite graphs
Prove that a bipartite graph $G = \left(V,E\right)$ has a perfect matching $\iff$ $\vert N(S)\vert\geq \vert S \vert $ for all $S \subseteq V$. (For any set $S$ of vertices in $G$ we define the ...
- 852
1
vote
1
answer
725
views
bipartite graph matching exercise
I have a problem here and would appreciate your help.
I have a bipartite graph $G = (A \cup B,E)$ which has a matching $M$ of size $|A|$. We need to prove there's a vertex in $A$ such that each ...
- 11
0
votes
1
answer
296
views
In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that $\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $
In a bipartite graph $G$ with bipartite sets $X$ and $Y$, prove that
$\alpha'(G)=|X|-\max_{S \subset X}(|S|-|N(S)|) $
No idea how to approach this one...any leads please?
- 849
4
votes
1
answer
440
views
Envy-free matching
Let $G \left(X, Y, E\right)$ be a bipartite graph with two equal-sized parts (that is, $|X|=|Y|=n$).
An envy-free matching is a perfect matching between two subsets $X_1 \subseteq X$ and $Y_1 \...
- 10.8k
3
votes
1
answer
1k
views
Hall's marriage theorem explanation
I stumbled upon this page in Wikipedia about Hall's marriage theorem:
The standard example of an application of the marriage theorem is to imagine two groups; one of n men, and one of n women. For ...
- 1,093
1
vote
1
answer
349
views
Matching Graph Drawing
How could I draw a graph that is connected, $3$-regular that has both a cut vertex and a perfect matching? I know every simple $3$-regular graph with no cut-edge has a perfect matching, but not sure ...
- 491
2
votes
6
answers
3k
views
Show the union of two matching is bipartite
Let $G=(V,E)$ be a graph.
Let $M1, M2$ be two matchings of $G$. Consider the new graph $G' = (V, M1 ∪ M2)$ (i.e. on the same vertex set, whose edges consist of all the edges that appear in either $M1$...
- 373
3
votes
3
answers
2k
views
Size of matching
Prove that every graph G without isolated vertices has a matching of size at least ${n(G)\over 1+∆(G)}$. (Hint: Apply induction on $e(G)$).
I know that a perfect matching is the size of a minimum ...
- 163
2
votes
1
answer
999
views
bipartite graph matching
can anybody please give me a hand on this lemma on bipartite graph matching please?
Let $M_1$ and $M_2$ be two arbitrary matchings in a bipartite graph G with bipartition $\{P,Q\}$ (of its vertex set)...
- 131
4
votes
2
answers
1k
views
Matching in bipartite graphs
I'm studying graph theory and the follow question is driving me crazy. Any hint in any direction would be appreciated.
Here is the question:
Let $G = G[X, Y]$ be a bipartite graph in which each ...
- 1,529
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
4
votes
1
answer
318
views
Complexity of counting the number of Good-perfect matching in bipartite graph
Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$.
Definition1: ...
user5409