Thread: Graph theory - perfect matching using Petersen's theorem

HI guys ,

I have a little problem regarding Perfect Matching .
I have a graph G=(V,E) with |V|=2n and δ(G)>=n (where δ(G) is the minimal degree
for each vertex) .
Now I need to prove that G has a perfect matching .

I tried to use Perersen's theorem for 3-regular graph but I kinda got lost (Petersen graph - Wikipedia, the free encyclopedia

can I say that if I separate the 2n vertexes that I have to 2 groups , S and T ,
then that the worst case scenario would be that : S would have at least two
neighbors in T , and further more , that there would be NO bridges ?

I cannot understand why , if we take some vertex , in would have a least two neighbors ??!!

if so , then now I want to use Petersen's theorem : if there are no bridges , is it right to say that any n-regular graph would have a 3-regular graph ?

I'll appreciate your help
thanks (:

Here is a different approach:

We use Tutte's theorem for the proof: Tutte theorem - Wikipedia, the free encyclopedia

We make a stronger claim : For any graph G(V,E) with |V|=2n and , for any subset S of V, the number of components in V\S is at most |S|.

Proof:The claim is obvious for |S| n.

For some S' such that S' < n, let |S'| = s. Let us assume that the number of components in V / S is more than s.

Due to the lower bound on the minimum degree, the size of each component must be at least ( n + 1 - s ). So the total number of vertices in G is at least Differentiating this function with respect to s, we find that it attains only one local extremum which is a maximum point at s = . Since it evaluates to (2n + 1) at both s=1 and s=n, it cannot have a lesser value in between.

This proves the claim and the required result follows by Tutte's theorem.