I'm interested in determining how many edges are required in a graph in order to be certain that a perfect matching exists. I'm thinking of a general graph, not a bipartite graph. The conditions are that the number of vertices is even, and that the degree of any vertex can't be higher than a particular, pre-selected value. For example, how many edges are required in a graph consisting of 10 vertices, with no vertex higher than degree 4, to be certain that a perfect matching exists?

I hope this is a proper way to respond to answers on this site (first time here). Thanks for the feedback. I should have included that the graph is assumed to be connected. Also, yes, I want to know how many edges are sufficient, for a particular number of vertices and maximum vertex degree, for a perfect matching to exist.

  • 3
    $\begingroup$ Have you considered the possibility that there may be no perfect matching given the requirements you have imposed? For example let G be the disjoint union of 2 K_5s. Then |G|=10 and G is 4-regular, but contains no perfect matching. $\endgroup$ – Ben Derrett Jun 26 '11 at 15:12
  • 2
    $\begingroup$ A graph which admits a perfect matching necessarily has $\# E \geq \frac{1}{2} \# V$, and this inequality is sharp. You are asking how many edges are sufficient for a perfect matching, right? $\endgroup$ – Pete L. Clark Jun 26 '11 at 15:18
  • $\begingroup$ A response to your first edit: As suggested in my first comment, in some cases (such as the one you supplied), there is no sufficient number of edges. Remember that a graph of the form you require has at most dn/2 edges, where d is the max. degree and n is the degree of the graph. $\endgroup$ – Ben Derrett Jun 26 '11 at 20:05
  • $\begingroup$ If connected, and based on Ha01's observation below, instead of having two isolated vertices, have two vertices of degree 1 which are both joined to the same third vertex. Then you can't match both of them (they both want the same partner). The rest of the graph can have as many edges as you like. $\endgroup$ – Mark Bennet Jun 26 '11 at 22:10

The literature about matchings, in particular perfect mathchings is vast. There is a classic book of Lovasz and Plummer: http://books.google.com/books/about/Matching_theory.html?id=yW3WSVq8ygcC

and this paper may also be of interest:



Claim: The maximum size (number of edges) for connected graph $|G|=2k$ and $\Delta(G)=d$ to have no perfect matching is at least $dk-d$. For large $k$ the maximum size is $dk$, which is optimal.

Let $G$ be a connected graph of order $|G|=n=2k$.
Let the maximum degree be $\Delta(G)=d$.
If $d=1$, then the graph is disconnected.
If $d=2$, then it is either disconnected or an even cycle, which has a perfect matching.
(Minimum size to be connected is $2k-1$)
In addition, there is a theorem that if $d(u)+d(v)\geq 2k$ for every non-adjacent $u,v\in V(G)$, then $G$ is Hamiltonian, which surely has a perfect matching.
(A converse of Dirac's theorem.)
Hence we need to further restrict $d< k$.
Hence we assume $3\leq d<k$.

Let $m$ be the maximum size such that there is no perfect matching.
As Ben Derrett has pointed out, $m\leq dn/2=d(2k)/2=dk$.

Since $G$ has no perfect matching, by Tutt's theorem $|X|<o(G-X)$ for some $X\subseteq G$.
For all such possible $X$, consider the case with largest $|X|$.
Suppose $|X|=k-1$. (It cannot be $>k-1$, else there are not enough odd components.)
For convenience, we let $G-X=W$.
Then $W=\lbrace u_1,\dots,u_{k+1}\rbrace$ and $X=\lbrace v_1,\dots,v_{k-1}\rbrace$.

Since maximum degree is $d$, there are at most $d(k-1)=dk-d$ edges from $X$.
This happens when all edges are from $X$ to $W$.
Given that $d=3$, we may construct the $dk-d$ edges such that $G$ is connected.
Start with a path $P=u_1,v_1,u_2,v_2,\dots,u_{k-1},v_{k-1},u_k$, then add edge $v_{k-1}u_{k+1}$.
This ensures connectedness.
The remaining edges from $X$ to $W$ may be set arbitrarily.
We know the requirement of max degree $d$ can be met as $|W|>|X|$.

However, after setting $dk-k$ edges, we cannot add any more.
Suppose instead that we add one more edge.
If cannot be from $X$ since all vertices are saturated.
Hence the edge is from $W$ to $W$.
But we may then check that $|X|<o(G-X)$ cannot be fulfilled.
Hence for the case where $|X|=k-1$, the maximum number of edges is $dk-d$.
Note: if we were to add more edges, then $|X|=r<k-1$.

Edit: The case where $|X|=r<k-1$ seems to be the complicated part.
This seems to depend on the relative values of $d$ and $k$.
For example, I can find a graph of $|G|=16,m=24$ and $\Delta(G)=3$ with no perfect matching.
It should be possible to have $dk$ edges if $k$ is large enough.
(Something like $2k>3d$.)
Given that $d<k$, so that you have $2d<2k$ to work with, this is pretty close.

Extra: For the general case without restriction on $d$, the maximum size also depends on $k$.
It may be checked that $m=3,10,19$ for $2k=4,6,8$ to have no perfect matching.
After that, $m=(k-2)(k-3)/2 + 2$.
This is by having a $K_{k-2}$ complete graph and last 2 vertices connected to $w\in K_{k-2}$.

  • $\begingroup$ In the general case , you have $ m = (k-1)(2k-1)+1$ . The tight example is $K_{2k-1}$ plus an isolated vertex. You can prove that if $m=(k-1)(2k-1)+2$ we must have an hamiltonian cycle. So If if have $m=(k-1)(2k-1)+1$, then adding one vertex would give hamiltonian cycle, meaning we must have hamiltonian path , this path is odd and it visits each vertex twice. From here it is pretty easy to see that we can find a perfect matching. $\endgroup$ – UserB95 Jul 30 '15 at 7:36

I think that the optimal graph (maximum number of edges but no matching exists) will have one or two vertices disconnected from the rest.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.