# Questions tagged [perfect-matchings]

A perfect matching is a matching of all the vertices of a graph. In other words, a perfect matching is a set of edges such that each vertex of the graph is incident to exactly one edge in the set.

82
questions

**1**

vote

**0**answers

25 views

### Finding minimum weight perfect matchings in sparse bipartite graphs

Question:
What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?
I am looking for ...

**0**

votes

**0**answers

13 views

### Find maximum directed graph

For a directed graph $G=(V,E)$, we want to compute the max number $k$ such that there exists a directed graph $H=(V,E')$ such that $E'\subseteq V\times V$ and $|E'|=k$ such that
For any $v\in V$, $(v,...

**2**

votes

**0**answers

44 views

### How to prove polynomial inequality encoded from 1-factors in $K_{2n}$

Let $G=(V,E)$ be a complete graph $K_{2n}$ and it has $m$ 1-factors $f_{i,(i=1,\dots,m)}$, where $m=\frac{(2n)!}{n!2^n}$.
Some definition:
$F=\{f_{1},f_{2},...,f_{2n-1}\}$ is one 1-factorization in $...

**-1**

votes

**1**answer

42 views

### What is known about iterated matching as a TSP heuristic

A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...

**5**

votes

**3**answers

295 views

### Can local flip moves connect dimer matchings on 'quadrangulated' planar bipartite graphs? (perfect matching reconfiguration problem)

I'm interested in the structure of dimer matchings on planar graphs with a bipartite structure. In particular, I'm interested in whether any two perfect matchings can be connected, i.e. transformed ...

**4**

votes

**0**answers

77 views

### Hypergraphs with only disjoint perfect matchings

Let $H(n,r)$ be the set of $r$-uniform hypergraph with $n$ vertices that have only disjoint perfect matchings (i.e. every hyperedge only appears in at most one of the perfect matchings). Let $m(h(n,r))...

**2**

votes

**1**answer

93 views

### Extending perfect matchings into Hamiltonian cycles

Let $G$ be a simple cubic graph which has a Hamiltonian circuit $C$. In general, it is not possible to find a second Hamiltonian circuit which contains all the chords of $C$. For example, the Wagner ...

**0**

votes

**0**answers

19 views

### What is the quality of this greedy algorithm for minimum weight cycle covers in complete graphs

Let $G$ be a complete graph with $n=2k,\ k\ge 2$ vertices; then first idea for a greedy minimum weight cycle cover $C_0$ is to take the union of the minimum weigt matching $M_0$ of $G$ and of the ...

**0**

votes

**0**answers

37 views

### Algorithmic complexity of deciding the existence of regular $\mathrm{f}$-factors in graphs

Finding regular $\mathrm{f}$-factors in undirected simple graphs can be reduced to finding a perfect matching by utilizing the gadgets of Tutte or of Lovász and Plummer; there are several algorithms ...

**0**

votes

**1**answer

66 views

### Combining three matchings to form a maximal matching

Consider a regular tripartite graph $G$ with maximum degree $\Delta\ge3$ and parts $A,B,C$. Now, the induced subgraphs $A\cup B, B\cup C$ and $A\cup C$ are all bipartite.
Now, is there a way to ...

**-2**

votes

**2**answers

204 views

### Cardinality of a set of mutually disjoint perfect matchings of $K_\omega$

If $G=(V,E)$ is a simple, undirected graph, we say that $M\subseteq E$ is a perfect matching if the members of $M$ are pairwise disjoint and $\bigcup M = V$. Let $K_\omega$ be the complete graph on $\...

**0**

votes

**1**answer

84 views

### A vertex transitive graph has a near perfect/ matching missing an independent set of vertices

Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...

**1**

vote

**0**answers

99 views

### A simple case of a strong version of the Berge-Fulkerson conjecture

UPDATE 28 June 2019 A counterexample for Conjecture 2 has been provided. The conjecture is now demoted again to guess. The text has been updated to reflect this change, and there is now a new ...

**1**

vote

**0**answers

33 views

### Perfect matchings and edge cuts in cubic graphs - part 1

Let $G$ be a bridgeless cubic (simple) graph, and let $M$ be a perfect matching in $G$. $G-M$ will necessarily be a set of circuits. For example, if we delete a perfect matching from $K_{3,3}$ we ...

**1**

vote

**1**answer

63 views

### Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph

What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...

**5**

votes

**1**answer

174 views

### On optimal dual solutions for the minimum weight perfect matching problems in the case of metric weights

Following Lovasz-Plummer (Matching theory, North-Holland 1986, Theorem 9.2.1),
the minimum weight perfect matching problem on a complete graph
$G$ with even number of vertices and weight $w:E(G)\to
\...

**2**

votes

**0**answers

49 views

### Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?

Planar graph permanent can be reduced to determinants and so statistics should be amenable.
Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new ...

**2**

votes

**1**answer

82 views

### Number of distinct perfect matchings/near perfect matchings in an induced subgraph

Consider a Class 1 graph with degree $\Delta\ge3$ and the induced subgraph formed by deleting a set of independent vertices of cardinality $\left\lfloor\frac{n}{\Delta}\right\rfloor$. Then, what is ...

**0**

votes

**0**answers

38 views

### Do all induced subgraphs of powers of cycles have a perfect matching

Do all independence induced subgraphs of powers of cycles have a distinct 1-factor? By independence induced, I mean those induced subgraphs which are formed by removing a maximal independent set of ...

**9**

votes

**0**answers

521 views

### Has this notion of vertex-coloring of graphs been studied?

In a study of a quantum physics problem, I came about an apparently very natural type of vertex colorings of a graph. The colors of the vertex $v_i$ is inherited from perfect matchings $PM$ of an edge-...

**3**

votes

**1**answer

245 views

### Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...

**22**

votes

**1**answer

1k views

### Vertex coloring inherited from perfect matchings (motivated by quantum physics)

Added (24.08.2019): As I consider this question important for quantum physics, I have announced a 3000 Euro award on its solution, see here for more details.
Added (19.09.2019): This problem can be ...

**2**

votes

**1**answer

49 views

### Triangle Center from Weighted Perfect Matchings

let $\Delta$ be the triangle whose corners $A$, $B$, $C$ points in general position in Euclidean plane and, let $D$ be a fourth point inside $\Delta$.
Question:
what is known about the ...

**7**

votes

**1**answer

217 views

### Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

The sequence A006318 at OEIS stands for the Schröder numbers.
They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...

**2**

votes

**0**answers

34 views

### Can Orientability of Manifolds be Generalized to TSP Instances?

It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular ...

**1**

vote

**0**answers

22 views

### Complexity of Calculating Minimum Weight Final Perfect Matchings

It is known, that Minimum Weight Perfect Matching can be calculated in $O(n^3)$;
Furthermore, it is possible, that the edge sets of the Minimum Weight Perfect Matching and of the Maximum Weight ...

**6**

votes

**1**answer

134 views

### Why is the number of Hamiltonian Cycles of n-octahedron equivalent to the number of Perfect Matching in specific family of Graphs?

In OEIS A003436, it is written that the number of inequivalent labeled Hamilton Cycles of an n-dimesnional Octahedron is the same as the number of Perfect Matchings in a the complement of the Cycle ...

**11**

votes

**1**answer

523 views

### Graphs with only disjoint perfect matchings, with coloring

The following purely graph-theoretic question is motivated by quantum mechanics.
Definitions: A bi-colored graph $G$ is an undirected graph where every edge is colored. An edge can either be ...

**-2**

votes

**1**answer

345 views

### Infinite graphs with large degree but no perfect matching [duplicate]

Is there an example of an infinite connected, simple, undirected graph $G = (V,E)$ such that every vertex has $|V|$ neighbors, but $G$ does not have a perfect matching (that is, a set $M\subseteq E$ ...

**9**

votes

**2**answers

271 views

### How to characterize “matching-transitive” regular graphs?

I am interested in regular graphs $G$ such that for each pair of 1-factors (=perfect matchings) $F$ and $F'$ there is an automorphism of $G$ that takes $F$ to $F'$. Let's call this property matching ...

**6**

votes

**1**answer

282 views

### Complexity for calculating number of Perfect Matchings in k-regular hypergraph

Let $G(V,E)$ be a unweighted, k-regular hypergraph, with vertices $V=(v_1, ... v_n)$ and edges $E=(e_1, ... e_m)$. The k-regularity leads to $|e_i|=k$ (i.e. every edge contains exactly $k$ vertices).
...

**-2**

votes

**1**answer

72 views

### Matching and minimal degree

Let $n\in\mathbb{N}$ be a positive integer and let $G =(V,E)$ be a connected simple undirected graph with $|V| = 2n$. Is it true that if for the minimal degree $\delta(G)$ we have $\delta(G) \geq n$, ...

**-4**

votes

**1**answer

126 views

### Connected infinite graph $G$ with $\delta(G)\geq 2$ and no perfect matching [closed]

Is there a connected infinite graph $G=(V,E)$ such that $\text{deg}(v) \geq 2$ for all $v\in V$, and $G$ possesses no perfect matching?

**2**

votes

**1**answer

247 views

### Perfect matchings in infinite graphs

Let $G=(V,E)$ be an infinite graph such that $|V| = \kappa$ for some infinite cardinal $\kappa$, and every $v\in V$ has degree $\kappa$. Does $G$ have a perfect matching?

**-3**

votes

**1**answer

120 views

### Does the Hadwiger-Nelson graph have a perfect matching?

The Hadwiger-Nelson graph on $\mathbb{R}^n$ is defined to be $(\mathbb{R}^n,E_n)$ where $$E_n = \big\{\{x,y\}: x,y\in \mathbb{R}^n \text{ and } |x-y|=1\big\},$$ where $|\cdot|$ denotes the Euclidean ...

**23**

votes

**3**answers

1k views

### Is every positive integer the permanent of some 0-1 matrix?

In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...

**7**

votes

**1**answer

471 views

### Graph to Bipartite conversion preserving number of perfect matchings

Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...

**6**

votes

**5**answers

2k views

### Applications of Perfect Matching

I'm exploring some applications of perfect matching and I would like some input. I have found many applications in chemistry (storing information, estimating bond lengths, estimating resonance energy, ...

**5**

votes

**2**answers

362 views

### Maximum number of perfect matchings in a planar graph?

What is the maximum number of perfect matchings a planar $k$-partite $|V|$ number of vertices simple graph can have where $k=2,3,4$ ($k>4$ is impossible for a planar graph)?
Since number of ...

**2**

votes

**0**answers

57 views

### Minimum size of genus $g$ bipartite graphs with $2^n$ perfect matchings

Given $n\in\Bbb Z_{\geq0}$ let $2T_{n,g}$ be size of smallest number of vertices of genus $g$ bipartite graph with $T_{n,g}$ vertices of each color such that number of perfect matchings is $2^n$.
Eg: ...

**3**

votes

**2**answers

624 views

### Applications of Hafnians

I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...

**8**

votes

**1**answer

271 views

### Fastest algorithm for counting perfect matchings in a general graph

Let $G(V,E)$ be a undirected graph. I am interested in the fastest known algorithm for counting the number of perfect matchings in $G(V,E)$ (which is known to be in $\#P$). In particular, what is the ...

**3**

votes

**1**answer

149 views

### Unique matching completion

Assume we have bridgeless cubic graph $G(V, E)$, $n=|V|$.
By Petersen's theorem, every such graph has a perfect matching.
Moreover, given any edge in $G$ there exists a perfect matching containing ...

**18**

votes

**2**answers

2k views

### Graphs with only disjoint perfect matchings

Let $G(V,E)$ be a graph. I am searching for graphs with only disjoint perfect matchings (i.e. every edge only appears in at most one of the perfect matchings).
Examples:
Cyclic graph $C_n$ with even ...

**4**

votes

**2**answers

927 views

### Edmond's blossom algorithm for Max weight perfect matchings

Edmond's blossom algorithm computes a maximum weight matching in a general graph (https://en.wikipedia.org/wiki/Blossom_algorithm).
Many papers also reference to Edmond's blossom algorithm to compute ...

**3**

votes

**1**answer

1k views

### Number of perfect matchings in bipartite graph with given minimum degree

Let $G$ be a spanning subgraph of $K_{n,n}$ with minimum degree $\delta(G) \geq n/2$. It's easy to show using Hall's theorem that $G$ has a perfect matching, and the example of two disjoint copies of ...

**1**

vote

**2**answers

138 views

### Reference Request: “Resolutions” of $K_n$ for $n$ odd

A resolution (in the combinatorial design sense) of $K_{n}$ is a collection of sets of edges of $K_{n}$ so that within each set of edges, each vertex appears once, and over the entire collection, each ...

**7**

votes

**0**answers

329 views

### Missing count in number of perfect matchings

Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$.
...

**1**

vote

**0**answers

145 views

### On Schrijver's lower bound for the number of perfect matchings

Schrijver's lower bound gives the number of perfect matchings in a $k$-regular bipartite graph as $\Big(\frac{(k-1)^{k-1}}{k^{k-2}}\Big)^n$. What is the corresponding lower bound for minimum-degree $k$...

**1**

vote

**0**answers

127 views

### Expected number of perfect matchings in bounded degree bipartite graphs

Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...