In a graph \(G\), we call a
matching any choice of edges in \(G\) in such a way that all vertices have
only one edge among chosen connected to them. A perfect
matching is a matching which is arranged on all vertices of the
graph.
Let \(G\) be a graph with \(2n\) vertices and all the vertices have
degree at least \(n\) (the number of
edges exiting the vertex). Prove that one can choose a perfect matching
in \(G\).