# Questions tagged [matching-theory]

For questions about matchings in graphs.

533 questions
Filter by
Sorted by
Tagged with
44 views

### In a simple graph with $2m$ vertices and a unique perfect matching, prove that $|E(G)|$ is bounded by $m^2$.

I have been trying to solve this question, it was already asked but the response seems to have some issues. The accepted answer implies that if a graph has a cycle of length 4, this implies that it ...
8 views

### Is the following claim on saturated matching on bipartite graphs with constrained degree true?

Claim: A bipartite graph $G(X, Y)$ with all vertices in $X$ having degree less than or equal to 2 has an X saturating matching if and only if for any components $G'(X', Y')$ in $G$, $|X'| \geq |Y'|$. ...
30 views

### Understanding the proof perfect matching polytope

Theorem. Let $M$ and $N$ be perfect matchings in a graph $G=(V, E)$. Then $\chi^M$ and $\chi^N$ are adjacent vertices of the perfect matching polytope if and only if $M \triangle N$ is a circuit. ...
1 vote
27 views

### Understanding the proof of Konig edge-colouring theorem

Theorem: (König's edge-colouring theorem). For any bipartite graph $G=(V, E)$, $$\chi(G)=\Delta(G) .$$ That is, the edge-colouring number of a bipartite graph is equal to its maximum degree. Proof. ...
52 views

### Prove that symmetric difference of two perfect matchings is union of disjoint even cycles

Problem: Let $M$ and $N$ be perfect matchings of a finite graph $G$. Prove that their symmetric difference is a union of disjoint even cycles. My attempt: Firstly, if $M = N$, we are done. Now, let us ...
20 views

### Algorithm for k sized matching in a complet weighted graph

as the Title suggest im looking for an algorithm for k sized matching in a weighted complet graph. Any further literature is welcome.
45 views

### Is there a way to do the Hungarian algorithm in reverse?

The Hungarian algorithm is used to find the optimal choices for a given 'cost matrix' e.g. going from the output of the Hungarian algorithm ...
1 vote
42 views

### What is the connection between the deficiency in bipartite graphs and the connected components? (Matching Theory, Lovasz, 3.3.13)

I am working my way through "Matching Theory" by Lovasz and Plummer. Lemma 3.3.13 is where I am stuck. Let $G$ be a graph such that $C(G)=\emptyset$ and let $X$ and $Y$ be barriers such that ...
59 views

### Find an alternating cycle in a graph with perfect matching.

Given a graph $G(V,E)$, we consider that there is a perfect matching $M$ in $G$. The edges in $M$ is red and the edges not in $M$ is blue. So is there a polynomial time algorithm that can find a red-...
23 views

### Hall's Bipartite Matching With All Pairs of Vertices Having Distinct Degree

Problem: $G$ is a bipartite graph having partite sets $U$ and $W$ where $|U|$ = $|W|$ = $k \geq 2$. I need to prove that if every two vertices of $U$ have distinct degree in $G$, then $G$ contains a ...
102 views

### Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched

Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the ...
39 views

### I can't find a proof of this graph theorem about matchings, would anyone be able to prove it?

Here is the theorem: Suppose $M_1, M_2, . . . , M_k$ is a sequence of matchings in a graph $G$ such that $M_i$ is obtained from $M_{i−1}$ by augmenting along some alternating path. If there is no ...
71 views

39 views

### Is the stable marriage problem defined for $0$ people?

When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
30 views

1 vote
50 views

### Hall's marriage, a question

The question is below: At a bakery the baker made 20 kind of cookies, from each kind he made exactly 20 cookies. Once baked, he randomly put them at 20 table pans, at each table pan he put exactly 20 ...
274 views

### Generalizing Hall's marriage theorem

(This question has been posted on mathoverflow: Generalizing Hall's marriage theorem) Fix positive integers $m,n,k$ such that $n\geq k$. Consider a bipartite graph between two sets of vertices $A$ and ...
26 views

50 views

### Solve problem with finding a matching. [duplicate]

Let $k<\frac{n}2$, prove there is a one to one function: $f: {[n] \choose k} \rightarrow {[n] \choose k+1}$, such that $A$ is a subgroup of $f(A)$ for every subgroup $A$ of $k$. I tried to make a ...
1 vote
195 views

### Criteria for infeasibility of bipartite graph full matching/linear sum assignment

I am trying to (programmatically) find a minimum weight matching in a large bipartite graph (over a thousand nodes on both sides with over a million edges), and I run into an issue where the "...
### 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 ...
Let $G$ be a graph and let $v$ be a vertex of $G$. Let $\alpha'(G)$ denote the size of maximaum matchings in $G$. My question is the following: Question 1. What is the maximum value of \$\alpha'(G) - \...