3
$\begingroup$

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
    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.2011-06-26
  • 2
    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?2011-06-26
  • 0
    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.2011-06-26
  • 0
    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.2011-06-26

3 Answers 3