Questions tagged [matching-theory]

For questions about matchings in graphs.

Filter by
Sorted by
Tagged with
0
votes
1answer
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: ...
0
votes
0answers
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?
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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$ ...
1
vote
2answers
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 ...
10
votes
4answers
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; ...
2
votes
1answer
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 ...
1
vote
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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....
0
votes
0answers
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 ...
1
vote
1answer
69 views

Maximum number of edges of a bipartite connected graph with vertex classes of size $n$ and with no perfect matching

At most how many edges can a connected bipartite graph with $n$ vertices in each class can have so that there is no perfect matching? If we omit the connectedness condition, then the maximum is $n(n-1)...
1
vote
1answer
33 views

Matching in bipartite graph $|M|\geq \frac {n}{\Delta (G)}$.

Given a bipartite graph, with n edges. Prove that there exist matching M such that $|M|\geq \frac {n}{\Delta (G)}$. Can someone check my solution. Can this be proved by induction, over $\Delta$. For, $...
1
vote
1answer
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 ...
0
votes
0answers
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
19 views

Barrier and Maximal Matching of a Graph

In Graph Theory lecture, I'm struggling to solve the problem about the maximal matching of a graph, form the textbook written by Bondy & Murty. Let $M$ be a matching of a graph $G$, and let $B \...
0
votes
1answer
26 views

Show that if a Bipartite Graph's minimum degree is equal to n, then the Bipartite Graph's matching consists of at least n edges

It is absolutely intuitive that it has to be the case, but besides drawing (an example) a Bipartite Graph for |X|=3 and |Y|=3 and showing that for |X|=3 and |Y|=3, |X|=3 and |Y|=4 and |X|=4 and |Y|=4 ...
1
vote
1answer
42 views

How to write the dual problem (for stable matching)

How do you write the dual of the following problem - I know the basics behind the Lagrangian function but I'm getting a little confused with how to handle the Lagrangian multipliers when we are ...
2
votes
1answer
32 views

Determining the most possible number of winners in a raffle

Every year we do a raffle at my job with prizes that were donated by local businesses. Everyone can select 5 prizes they'd like to win from a total of x number of prizes. After that a winner is ...
0
votes
0answers
23 views

Maximal vs. maximum sized matchings

This question should be an easy one :) I couldn't find it already in stackexchange so thought it would be worth asking. As I understand it: A Maximal Matching cannot be extended (i.e. it is not a ...
2
votes
1answer
29 views

Dirac's theroem for bipartite graphs

The theorem of Dirac that any graph $G$ on $n\geq 3$ vertices with minimum degree $\delta(G)≥n/2$ contains a Hamilton cycle is one of the classical results of graph theory. Is there are analogous ...
1
vote
0answers
44 views

Minimum vertex degree of a graph divided by 2 is smaller than maximum matching

Let G be a simple graph. δ(G) is the minimum vertex degree. Prove that if M is the maximum matching, then δ(G)/2 ≤ |M|. How to prove this?
1
vote
1answer
30 views

Maximal Matching in Bipartite Graph with Degrees Given

I'm quite stuck on how to go about showing the second part of the following question: Assume $G(V,E)$ is a bipartite graph with bipartition $V = P\cup Q$ and every vertex in $P$ has degree $a$, and ...
1
vote
1answer
56 views

Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. Show that if $ H $ has a perfect matching, then $ G $ has a perfect matching .

Let $ G $ be a connected graph and $ C $ be an odd-length cycle in G. We define graph $H$ as follows: $$ V (H) = {{(V (G) - V (C)) ∪ {c}}}, $$ where $ c $ is a new vertex that we add arbitrarily $$ E ...
1
vote
1answer
51 views

Partitioning vertices in biregular graph

This is the continuation of the previous question. Consider a $(a,b)$-biregular graph $(X,Y,E)$. In this case, $a|X|=b|Y|$ holds. Assume that $g:=|Y|/a=|X|/b$ is an integer. Further, assume that $|X|\...
1
vote
1answer
67 views

Hall bigamy problem.

I'm looking for a rigorous proof for Hall's bigamy problem: Let $G$ a bipartite graph with sides $V$ and $U$. Prove that you can match for any vertex in $V$ two vertices in $U$, that are matched ...
0
votes
2answers
57 views

One to many matching, using Hall's theorem?

I'm having a difficult time finding the neccessary and sufficient condition in the question and would love some help, I thought I had it but found a counter example for my "proof". The question is: ...
0
votes
0answers
37 views

Set theory question that suppose to relate to graph theory.

Let A1,...,Ak be k subsets of the set V={1, ..., n}. Find a necessary and a sufficient condition for the existance of a representative susbset B, meaning that for every subset there is a marked ...
2
votes
1answer
31 views

Matching of Vertices with Maximal Degree in Bipartite Graph

Let G be a bipartite graph and let A be the set of vertices of maximal degree. Show that there is a matching in G that covers A where A is not necessarily in one partite. I am trying to apply a ...
-1
votes
1answer
34 views

Blossom Algorithm

I have noticed that in the blossom algorithm, we need to find the blossom while finding the augmenting path. What will happen if I just know there is a blossom in a graph and the contracted graph has ...
4
votes
1answer
62 views

Reducing the Degrees of a Graph where All Degrees are Quite Concentrated

Suppose the degrees of all vertices in a graph $G$ (say, a bipartite graph) are all in a very concentrated range $[d(1 - o(1)), d(1 + o(1))]$, with $d$ an arbitrarily large constant. Here $o(1)$ is a ...
1
vote
1answer
38 views

Hall's Marriage Theorem question

I read Hall's marriage theorem from Discrete Mathematics by Rosen. I understood most of the theorem but have some questions on some parts of the proof : Question : In both cases when considering all ...
0
votes
0answers
27 views

Maximum matching in a hamilton graph of “k” vertices is always (k+1)/2 , is this claim correct?

My observation is : - Say for a(any) Hamilton graph of 1000 vertices , the value of its maximum matching will be 500 . Can somebody prove it or verify it ?
2
votes
3answers
87 views

Prove that at most one man obtains his worst choice in stable matching algorithm

For the Stable Matching algorithm by Gale-Shapley, how do I prove that at most one man will get his worst choice? My intuition is that I have to use contradiction. Assume that there are two men who ...
0
votes
1answer
28 views

How to calculate number of perfect matchings?

Assume that we have a bipartite graph called $G$ such that $G=(X, Y)$ and we have $X=\{x_1,\dots,x_n\}$ and $Y=\{y_1,\dots,y_n\}$. For each $1\leq i\leq n$, $x_i$ is adjacent to $\{y_1,\dots,y_n\}$ \ ...
2
votes
1answer
82 views

Perfect matching in a random bipartite graph with edge probability 1/2

I am trying to prove that, when given a bipartite graph $G=(X \cup Y, E)$ with $|X|=|Y|=n$ and edge probability $\frac{1}{2}$, as $n\rightarrow \infty$ the probability of the graph having a perfect ...
3
votes
2answers
34 views

Scheduling players in a team so that every player plays the same amount of time

I've been asked the following question: You are a basketball team manager, and the team consists of $8$ players. Every moment, exactly $5$ players have to be on the field. Given that a game duration ...
0
votes
0answers
22 views

Is the maximum matching LP totally dual integral?

Is the maximum matching LP ($\Gamma(S) $ is the set of edges with both endpoints in $S$, $\delta(S)$ is the set of edges with exactly one point in $S$) $$ 2\sum x_e \ \ \{ e \in E \} \\ s.t. \\...
6
votes
0answers
65 views

Extending a theorem from bipartite graphs to tripartite hypergraphs

Here is a useful theorem on bipartite graphs. Theorem. Let $G = (X\cup Y,E)$ be a bipartite graph with $n$ vertices in each side and positive weights on the edges. If for each vertex $v \in X\cup Y$,...
3
votes
2answers
63 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 $...
0
votes
0answers
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 ...
3
votes
0answers
41 views

Bipartite matching with degree and “budget” constraint

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 ...
0
votes
1answer
15 views

Edmond's perfect matching polytope odd subset condition

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 \...

1
2 3 4 5 6