Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was reading a result where the following proposition appears as a preliminary step (and left as exercise):

Claim: Suppose $G$ is a graph on $n$ vertices ($n$ even and $n \geqslant 3$) with minimum degree at least $n/2$. Show that $G$ contains a perfect matching.

Proof: By Dirac's theorem, $G$ has a Hamiltonian cycle $C$. Since $|C|=n$ is an even integer, the set of “odd” edges of $C$ gives a perfect matching for $G$. $\quad\Box$

I feel that using Dirac's theorem for this claim is an overkill. But after trying for a few days, couldn't come up with any other proofs. Can you give a more “direct” proof of the claim that avoids the machinery of Hamiltonian cycles?


Naturally, you might object to the vague requirement of “directness”. To clarify what I mean by it, I’ll give an example.

Claim 2. Suppose $G$ has a minimum degree at least $n/2$. Show that $G$ is connected.

Proof via Dirac's theorem. $G$ has a hamiltonian cycle as before, and hence is connected. $\Box$

A different proof. We'll show that any pair of vertices $u,v$ are connected by a path of length at most $2$. If $uv$ is an edge, we are done. Suppose not. Then $N(u) \cup N(v) \subseteq V \smallsetminus \{u,v\}$. Therefore $$ |N(u) \cap N(v)| = |N(u)| + |N(v)| - |N(u) \cup N(v)| \geqslant \frac{n}{2}+\frac{n}{2}-(n-2) = 2 \gt 0. $$ In particular there exists vertex $w$ such that $uw$ and $wv$ are both edges, and we are done. $\quad \Box$

I find the proof via Dirac's theorem much less illuminating in this example. In fact, as Qioachu points out below, the Claim 2 might even appear as an intermediate steps of Dirac’s theorem, making the above proof cyclic. My intention here is only to point out that Dirac’s theorem can be used as a powerful black box in killing much easier results.

share|improve this question
1  
The proof I know of Dirac's theorem needs a stronger version of Claim 2 as a lemma. –  Qiaochu Yuan Aug 8 '11 at 22:17
    
@Qia Admittedly its first "proof" of Claim 2 is a bit silly and circular. I guess my point is this: Sometimes the easiest way to convince yourself that you are not trying to show some false statement is to check that it is a corollary to some big hammer that you are sure to be true. However it's not the right or best way. –  Srivatsan Sep 13 '11 at 15:52

2 Answers 2

up vote 7 down vote accepted
+100

Here's an alternative proof using Hall's theorem -- I don't know whether that counts as a more "direct" proof, but at least it uses a theorem that directly deals with perfect matchings instead of a detour (pun intended) through Hamiltonian cycles.

Arbitrarily divide the vertices into two sets $A$ and $B$ of equal size. In each set, find a vertex with a minimal number of edges connecting it to the other set, and swap the two minimal vertices. Repeat this until the swap would no longer increase the total number of edges connecting the two sets. (Since there is a finite number of edges, this must happen at some point.) Denoting the two vertices whose swap would no longer increase the number of connections by $v_A$ and $v_B$ and the numbers of their edges within and between the sets by $v_{AA}$, $v_{AB}$, $v_{BA}$ and $v_{BB}$, and counting the number of connections between the sets before and after the swap, we have $v_{AB}+v_{BA}\ge v_{AA}+v_{BB}$. (There might be an edge between $v_A$ and $v_B$, but that works in favour of the inequality.) It follows that

$$v_{AB}+v_{BA}\ge \frac12(v_{AB}+v_{BA}+v_{AA}+v_{BB})=\frac12(\deg v_A+\deg v_B)\ge \frac12(n/2+n/2)=n/2\;.$$

Now consider a subset $X$ of $A$. If $|X|\le v_{AB}$, then since each element of $A$ has edges to at least $v_{AB}$ elements of $B$, $X$ has at least as many neighbours in $B$ as elements. If $|X|>v_{AB}$, then since each element of $B$ has edges to at least $v_{BA}$ elements of $A$ and $v_{AB}+v_{BA}\ge n/2=|A|$, at least one of these edges must lead to $X$, so $X$ has $n/2$ neighbours in $B$, and thus at least as many as it has elements. Thus the premise of Hall's theorem is fulfilled, and the bipartite graph induced on $A$ and $B$ must contain a perfect matching, which is also a perfect matching in $G$.

share|improve this answer
    
Very nice. I find your idea of reducing the problem from general matching to bipartite matching refreshing. (Sorry about the late response! :-)) –  Srivatsan Sep 13 '11 at 16:05

I believe it might be possible to provide a simpler proof by induction. Conisder the minimal situation where each vertex has degree $n/2$.

For the first case, $n=4$, this is equivalent to $C_4$ and there is an obvious perfect matching, and adding more edges between the vertices does not affect the existence of a matching.

Now consider the operation of adding 2 vertices ($u$ and $v$) and enough edges to a graph (which already contains a perfect matching) to fulfill the $n/2$ condition. If there is an edge between $u$ and $v$ add that edge to the matching and the matching is perefct.

If there is not an edge between the two new vertices then they must share at least 2 neigbors ($y$ and $z$) because there are $n$ original vertices and $u$ and $v$ must each dominate $\frac {n+2}{2}$ of these vertices. There are three further cases to consider.

Case 1 If the edge $yz$ is in the original matching then WLOG replace $yz$ with $uy$ and $vz$ and the matching is again perfect.

Case 2 If the edge $yz$ is not in the original matching and $u$ and $v$ share only 2 neighbors then create an augmenting path as follows: Select an alternating path from $y$ to $z$ taking the matched edge from $y$ as the first edge in the path. The vertex that is matched to $z$ ($p$) must be adjacent to either $u$ or $v$ because by only sharing 2 common neighbors $u$ and $v$ cover all of the vertices. WLOG assume the $v$ is adjacent $p$ and add $zp$ and $pv$ to the path. Add the edge $uy$ and the path becomes an augmenting path that when the edges are flipped creates a perfect matching.

Case 3 If $u$ and $v$ share more than 2 neighbors they must be adjacent to both ends of a matched edge. As in case 1 above you may remove that edge from the matching and replace with two edges of your choice attaching one of each $u$ and $v$ to an vertex from the previous matching.

share|improve this answer
    
I do not understand how to get the conclusion "..they must be adjacent to both ends of a matched edge" in Case 3. (Also, a nitpick in the beginning of the proof: it is not always possible to make the graph $n/2$-regular by removing edges. For instance, what if the graph has $\rm 2$ vertices $a,b$ with degrees $> n/2$ and remaining with degree $n/2$, such that $ab$ is not an edge?) –  Srivatsan Aug 30 '11 at 18:11
    
Thank you for your approach using induction. –  Srivatsan Aug 30 '11 at 18:16
    
@Srivatsan Narayanan- Your'e welcome. In the beginning I intended to simply use your claim #2 to consider only the least possible edges $n/2$ per vertex. There may certainly be more in the graph, they just aren't relevant to the proof. I should have been more explicit with my wording. In case #3 if $u$ and $v$ have multiple common neighbors you can use the pigeonhole principle to show that they must be commonly adjacent to at least one matched previously matched edge. –  user12998 Aug 31 '11 at 22:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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