# Questions tagged [matching-theory]

For questions about matchings in graphs.

280 questions
Filter by
Sorted by
Tagged with
46 views

### Rural Hospital Question

How to I prove that the algorithm for the Rural Hospital Problem is valid ( i.e. its finite and leads to a stable assignment of physicians to rural hospitals ) ?. Here is how the algorithm works: ...
26 views

### Independent zeros definition

I came across this definition in a graph theory book But I don’t get what $i_t,j_t$ means. Can someone explain?
45 views

### Is it possible to match two women to each man so that every women will not match more than once

I am new to this topic and I have no idea how to proceed. Any help ? Given a group of men and group of women. Every group of man $A$, $|A|$=$x$ knows a group of women $B$ and the cardinality of $B$ is ...
70 views

### Consider $G$ is a connected graph. For any vertex $v$ in $G$, prove that there exists a matching for which $v$ is saturated.

I couldn't think of any connected graphs where the property didn't hold, so assume it is true. However, I couldn't think of a formal proof. I tried doing this: Case I: If $G$ has an even number of ...
43 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$ ...
84 views

### Proving a graph doesn't have a perfect matching

Consider the following graph: Find a perfect matching or prove one doesn't exist. I don't think a perfect matching exists here, as the vertices $a_2, a_3$ and $a_4$ are problematic to us, but I'm ...
1k views

### Can you win the monochromatic urn game?

In the (monochromatic) urn depletion game, you are given $n$ vases, each containing some number of balls $a_1,\ldots, a_n \geq 0$. You win the game if you can remove all of the balls from the vases; ...
80 views

### $k$ regular graph with $(k+1)^2 -1$ vertices and matching saturates $n-k$ vertices

We have a $k$ regular graph $G$ with $n=(k+1)^2-1$ vertices and $k \geq 1$ is even. Prove that the graph has a matching saturates at least $n-k$ vertices. My first intuition is to use the defect ...
78 views

### Given a perfect fractional matching, does there exist a perfect matching with heavy edges?

Let $G = (X\cup Y, E)$ be a bipartite graph in which $|X|=|Y|=n$. Suppose $G$ admits a perfect fractional matching, that is - a function assigning a non-negative weight to each edge, such that the sum ...
20 views

### Matchings in bipartite graph

I was given the following statement: Be $G=(X \cup Y, E)$ a bipartite graph connected with $|X|=|Y|=4$ $|E|=7$ , all maximal matching in G is maximum. I must say if it is true or false and justify. By ...
37 views

### Different matchings in $K_{10}$, the complete graph with 10 vertices, with 4 edges [closed]

I ran into this graph theory/combinatorics problem, and I'm having some troubles finding the solution. Considering $K_{10}$, the complete graph with $10$ vertices, what is the number of different ...
31 views

### Matching graphs (Graph theory in discrete math)

For this exercise, you will need to do some research on matchings in graphs. Two chess clubs, A and B, are organizing a chess tournament. Suppose there is a natural number m such that each member of A ...
34 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 ...
32 views

### Let $\alpha_{1}$ denote the maximum number of edges in a matching. Prove that $\alpha_{1}=\min\{\delta(G),\lfloor\frac{|G|}{2}\rfloor\}$

Question about matches (Graph theory) : Let $\alpha_{1}$ denote the maximum number of edges in a matching. Prove that $\alpha_{1}=\min\{\delta(G),\left\lfloor\frac{|G|}2\right\rfloor\}$, if $G$ is a ...
53 views

### Hall's theorem usage

I got this question from my professor and I have no idea how to solve this, any help would be appreciated "12 politicians give speech every day. Everyone of them uses the same set of 12 arguments....
34 views

### Show that if a 2-edge-connected graph has a 1-factor, then it has at least two distinct 1-factor.

Show that if a 2-edge-connected graph has a 1-factor, then it has at least two distinct 1-factor. I found the next answer in this post 2-edge connected has perfect matching, then graph has two perfect ...
69 views

33 views

### matching in k-regular graph

I had been asked to prove that in k-regular graph exists a matching of size $n/4$ . I had read that answer Question about edge coloring and perfect matchings in regular graphs but I couldn't ...
10 views

### Correlation and dependence of random variables: The connection.

Before I state my question I want to give some background information about where my question comes from. I am currently reading the paper: Online Matching with General Arrivals by Gamlath, Kapralov, ...
32 views

### On the hard direction proof of Hall's theorem for bipartite graphs

The hard-direction proof of Hall's Theorem in bipartite graphs is given as follows (Source Wikipedia): We assume that there is no $X$-saturating matching and prove that Hall's condition is ...
32 views

### Factor-critical Graph and Its Blocks

I'm struggling to solve the statement: A Graph $G$ is factor-critical if and only if every block of $G$ is factor-critical. For the if part, I tried to use the property of blocks that, two distinct ...
19 views

18 views

### Augmenting Path and Matching

I am trying to get the maximum matching in a bipartite graph. I'm trying to apply Hopcroft–Karp algorithm (https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm). I have little confusion over ...
Consider a bipartite graph of vertices of people $P_1,P_2,\dots,P_p$ with edges connected to vertices of tasks tasks $T_1,T_2,\dots,T_t$. An edge from $P_i$ to $T_j$ means that the person $P_i$ can do ...
I'm a bit confused as to how the $K_3$ graph with $x(e) = \frac12$ for all $e \in E$ fails the third set of inequalities for Edmond's perfect matching polytope ($x(\delta(U)) \geq 1$ for each \$U \...