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