Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [matching-theory]

For questions about matchings in graphs.

0
votes
0answers
80 views

Hall's Theorem for infinite graphs (Compactness theorem)

To Proof: Let $G = (V,E)$ be an infinite bipartite graph with $V = S \overset{.}{\cup}T$ and finite node degree for each node. G has a matching, that covers a set S iff for all subset $H \subseteq ...
0
votes
0answers
24 views

Find the Ramsey number $R(G, P_3)$

Let $G$ be a graph with no isolates and $\lvert V(G)\rvert= m$ such that $\overline{G}$ has a perfect matching. I want to show that $R(G, P_3)=m$ Clearly, $R(G, P_3) \geq \lvert V(G) \rvert = m$, so ...
1
vote
1answer
22 views

Lower bounds on # of hyper-edges in a hyper-graph with many near-perfect matchings

Let $G = (V,E)$ be an $L$-uniform hypergraph, s.t.: $n := |V|$ $L$ divides $(n - 1)$ every subset of $V$ of size $(n - 1)$ has a perfect matching (which would be a near-perfect matching in $G$) Can ...
-1
votes
2answers
58 views

How to write the optimization constraint of the following problem

$A$ is an adjacency matrix and $W$ is the weight matrix. So the problem is to find the maximum matching, such that for those nodes are connected, the weight between them is limited by $d$, which $W_{...
5
votes
1answer
51 views

Assign a list L(x) of size two to every vertex x of an odd cycle. Show that there is an L-coloring unless all sets L(x) are the same.

The problem above is from a midterm that I just took in my graph theory class and I didn't know how to answer it. I was hoping to get some tips to better understand the problem and write it out. Thank ...
1
vote
1answer
46 views

Matching students with books, such that each student matches k books and each book matches k students

Every student has a list of k-many books they need to read, and each book is on the reading list of k-many students. Each day, each student borrows a book, reads it, and returns it that evening (so no ...
0
votes
0answers
13 views

Show in Gale-Shapleys that there is one unique matching iff male optimal = women optimal.

I am having trouble trying to come up with the proof for this problem. I know that i need to prove this implication both ways for when one unique match implies Man optimal match = women optimal match ...
1
vote
1answer
32 views

Question regarding perfect matchings in a graph

I have a connected, bridgeless graph with 72 vertices of degree 3 and 2 vertices of degree 2. Is there a way that I can prove that this graph has a perfect matching? From the graph I can see there is ...
3
votes
1answer
65 views

Game on a Graph

Assume a game on a Graph $G$ with two players called Alice and Bob. They alternate their moves and Alice always begins. In the beginning Alice puts a coin on arbitrarily vertex of the Graph. In ...
1
vote
1answer
42 views

Bipartite allocation with minimum cost

Given two vertex sets $V_1$ and $V_2$. The vertices in $V_2$ have a limitation on the maximum degree of each vertex being $K$. I need to find an allocation algorithm such that every pair of vertices ...
1
vote
1answer
42 views

Use min-cut max-flow to prove that the matching number $\alpha'(G)$ of a bipartite graph is equal to its vertex cover number $\beta(G)$

My approach is to construct a network on the bipartite graph, with the source and sink being two extra vertices, each adjacent to all vertices from one partition of G. All edges are "forward" edges, ...
1
vote
1answer
53 views

Does Kőnig's theorem hold for infinite bipartite graphs?

Kőnig's theorem states that in a bipartite graph the size of the maximal matching equals the size of the minimal vertex cover. I learned it as an equivalence to Hall's theorem and we proved it using ...
0
votes
0answers
6 views

Intuition re: Optimal matching distance

The optimal matching distance between the unordered sets $\lambda=\{\lambda_1,\ldots,\lambda_n\}$ and $\mu=\{\mu_1,\ldots,\mu_n\}$ is defined as $d(\lambda,\mu)=\min_{\sigma\in S_n}\max_{1\leq i\leq n}...
0
votes
0answers
17 views

Proving that the set of maximal-degree vertices of a Graph result in a matching for all vertices [duplicate]

A question on my Graph Theory Homework is as follows, and I'm unsure about how to start solving it. Any tips would be greatly appreciated. Consider a bipartite graph. If M ⊂ V be the vertices of ...
0
votes
1answer
49 views

Stable Matching Theorem

Let $G=(V,E)$ be a graph and let for each $v\in V$ let $\le_v$ be a total order on $\delta(v)$. A matching $M\subseteq E$ is stable, if for every edge $e\in E$ there is $f\in M$, s.t. $e\le_v f$ for a ...
0
votes
2answers
20 views

The matching number in powers of cycles

What can be said about the matching number of powers of cycles, $C_n^k$, where $n$ be even? I think powers of cycles do not have have perfect matching for $k\ge3$, for, these graphs have odd cycles. ...
3
votes
0answers
22 views

Balanced weight perfect matching

Given an undirected graph $G = (V,E)$, edge weight $w_e \ \forall e \in E$, I'm interested in the following problem. Find a perfect matching $M \subseteq E$ that minimizes $(\max_{e \in M} w_e - \...
0
votes
1answer
14 views

What can we say about graph G?

Let G be a bipartite graph that does not have a perfect matching, but if we add any new edge to G, then the new graph G+ is no longer bipartite, but has a perfect matching. What can G be? I found one ...
0
votes
0answers
28 views

Choice of augmenting path in the Augmenting Path Algorithm + Proof of correctness

I'm watching this video of an example of the Augmenting Path Algorithm. https://youtu.be/C9c8zEZXboA?t=240 For convenience, I name the vertices of X, from left to right, $x_1, x_2, x_3, x_4, x_5, x_6$...
1
vote
1answer
44 views

Exercise 6.5 on p.133 in “Introduction to Graph Theory 5th Edition” by Robin J. Wilson.

The definition of complete matching on p.129: More generally, a complete matching from $V_1$ to $V_2$ in a bipartite graph $G(V_1, V_2)$ is a one-one correspondence between the vertices in $V_1$ ...
1
vote
1answer
39 views

Is the converse true?

Let $G$ be a connected bipartite graph with partite sets $X$ and $Y$ such that cardinality of $X$ equals to cardinality of $Y$ $\geq$ 2. If every two vertices of $X$ have distinct degrees in $G$ then ...
3
votes
2answers
64 views

Perfect matchings in bipartite graphs.

Question: $G$ is a bipartite graph where $|X| = |Y| = n$ and $|E| \geq n^2 - \frac{2n}{3} + 3$. $X$ and $Y$ are the set of vertices and $E$ is the set of edges. Prove that $G$ has a perfect ...
1
vote
1answer
40 views

Unique matching in a bipartite graph

Let $K_{n,m}$ (m> n) have vertex set $ (V_i: i \in [n])$ and $ (W_i: i \in [m])$. Let f(n) be the number of distinct maximum matchings M in $K_{n,m}$ such that $V_iW_i$ is not in M for any $i \in [n]$ ...
1
vote
1answer
44 views

Prove that there exists a set $Y$ such that for every $v$, there exists $y \in Y$ that is incident to $v$.

Suppose $A,B,X$ are independent and disjoint sets of vertices in a graph such that $A \cup B \cup X = V$, $|A|=|B|=9$ and $|X| = 63$. Also, assume $d(v) = 7$ for every $v \in A,B$ and suppose that for ...
0
votes
0answers
16 views

How to set number of pairings in relation to cost

I'm applying an assignment algorithm to pair objects A with objects B. The result is a matching with a sum of minimum cost. I want to find out whether it makes sense to restrict the assignments in ...
1
vote
1answer
41 views

Identifying a Maximum matching and a minimum cover for a specific bipartite graph

I have been given the following matching: $$ M =\{ \{a,3\}, \{b,1\},\{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$ in the bipartite graph: The matching looks like: I applied the augmented path ...
0
votes
0answers
21 views

Maximum weight matching with repeated nodes

We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ...
0
votes
0answers
13 views

Proof of a Lemma for Saturated Non-Factorizable Graphs

I have the following queries about the lemma on saturated non-factorizable graphs. My attempt at constructing a saturated non-factorizable graph also seems to contradict the lemma. (The proof is ...
0
votes
0answers
98 views

Number of Perfect Matching in Complete Graph - Proof Explanation

Want to find the number of perfect matching in a complete graph K2n where 2n is the number of vertices: Came up with the following method - 1. Counting Edges ...
0
votes
1answer
22 views

Matching of size at least $\frac{|E(G)|}{3}$ in the line graph $L(G)$ of a graph $G$

Let $G$ be a loopless graph such that the degree of every vertex is even . Show that the line graph $L(G)$ of $G$ contains a matching of size at least $\frac{|E(G)|}{3}$. My attaimpt: By a theorem ...
0
votes
0answers
10 views

Lower bound for matchings hypergraphs

I found a lower bound on matchings in hypergraphs in Pikhurkos paper: Perfect Matchings and $K^3_4$-Tilings in Hypergraphs of Large Codegree The bound is obtained by the following construction. We ...
0
votes
1answer
56 views

Weaker version of Hall's condition

In chapter 1 of Lubotzky's "Discrete Groups, Expanding Graphs and Invariant Measures", remark 1.1.2, one definition of expanders is the following: if $n, k \in \mathbb{N}$ and $c \in \mathbb{R}_{> ...
2
votes
1answer
85 views

Perfect matching in random bipartite graph - with fixed probability

as a follow up from this question : Suppose that we have a simpler problem, where the probability $p$ is fixed. Of course we could use the above result to proove that almost every graph in the model ...
0
votes
1answer
18 views

Parity of vertex cover for a graph with 2p vertices

Let $G$ be a connected graph with $2p$ vertices. We want to show that $$\frac{|VertexCover|_{min}}{|MaximalMatching|}<2$$ I started like this : Let $G$ be a graph with $2p$ vertices such that $\...
0
votes
0answers
44 views

How many matchings does a cycle on n vertices have?

how many matchings does a cycle on n vertices have? this is graph theory. If n = 3, matching would be 3? and If n = 4, matching should be 4 and If n = 5, matching would be 10? It seems there is ...
0
votes
1answer
34 views

A graph with a disjoint matching contains components that are either paths or even circuits.

I wish to prove the following result: Let $M$ and $M'$ be disjoint matchings in a graph $G = (V,E)$. Show that every component of the graph $(V, M \cup M')$ is a path or an even circuit. We just ...
0
votes
1answer
18 views

The Maximum Path of a Graph Contained In Maximum Matching

I just started learning some basic graph theory stuff and I was wondering if the following claim/proof is valid and whether it has any implications. I want to show that the Maximum Path of any graph ...
0
votes
0answers
32 views

Does there exist an algorithm that outputs a maximum weight transversal and has a stable matching?

If you have some bipartite graph with an adjacency matrix that represents the weights of the edges of that particular bipartite graph, then the Hungarian algorithm outputs a maximum weight transversal....
1
vote
1answer
29 views

About $E_i$ in “An $n^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs” by Hopcroft and Karp

I am reading "An $n^{\frac{5}{2}}$ Algorithm for Maximum Matchings in Bipartite Graphs" by Hopcroft and Karp. And I cannot understand the following definition of $E_i$. Because $$\{(u, v) | (u, v) \...
0
votes
0answers
49 views

Optimal matching with halls marriage theorem

Hall’s marriage theorem says that a bipartite graph with vertex set $U ∪ V$ has a matching of size $|U |$ if and only if every subset $S ⊂ U$ has at least $|S|$ neighbours. Suppose that ${1, 2, 3, 4, ...
1
vote
1answer
63 views

Are there $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint?

I am reading a book about Graph Algorithms written by Takao Asano. In the book, the author says the following proposition is true, without a proof. Is the follwing proposition true or false? If true, ...
0
votes
1answer
25 views

Perfect matching in the n-unit-cube, Is hyperplane statement wrong?

I was thinking about perfect matchings in the graph of the unit-cube of dimension $n$: $Q_n = [0,1]^n$. ($0$-$1$-strings of length n are vertices. Two of such are connected by an edge iff. they differ ...
2
votes
1answer
39 views

About a proof of a proposition about maximum matching (Aho, Hopcroft, Ullman)

I am reading "Data Structures and Algorithms" by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The key observation is that $M$ is a maximal matching if and only if there is no augmenting ...
10
votes
4answers
1k views

A magic trick - find out the fifth card if four is given

Here is a magic trick I saw. My question is how the magician and his partner did it. Given the simple French deck of cards, with $52$ cards. A person from the audience chooses randomly five cards ...
1
vote
1answer
45 views

A problem based on Tutte's Theorem

Let $G$ be a simple graph, with order $\nu$ even and minimum degree $\delta <\nu/2$. Show that if number of edges ($\epsilon$) in the graph be such that $\epsilon$ > $\delta \choose 2$ + $\nu - 2\...
1
vote
1answer
40 views

What is the minimum number of matchings needed to cover all the edges of a graph?

Given a graph, what is the minimum number of matchings needed such that their union contains all the edges in the graph? Is it related to the degree of the graph?
0
votes
1answer
22 views

inadmissible bipartite graph

Consider the optimal perfect matching problem on a bipartite graph G= (X $\cup$ Y, E) with $\vert X \vert = \vert Y \vert$ and a weight function $w: E \to \mathbb{R}$. We want to find a perfect ...
1
vote
0answers
63 views

Existence of a path consisting of only essential/inessential vertices

When learning definition of essential and inessential vertices, out of curiosity, I am looking for a graph which contains a path that only consists of essential/inessential vertices. A vertex is ...
0
votes
1answer
34 views

An Efficient Minimum Distance Bipartite Matching Algorithm

For one of my works, I need a "minimum distance bipartite matching" algorithm, which I describe below: I have two disjoint sets $A$ and $B$ with $|A| = |B| = n$. The sets $A$ and $B$ are subsets of $\...
0
votes
0answers
42 views

Problem on Gallai-Edmond's decomposition.

Let $M$ be a matching in an undirected graph $G$. Let $v$ be an unmatched vertex in $(G, M)$. If there does not exist an augmenting path starting from $v$ in $(G, M)$, then show that there exists a ...