Let G be a bipartite graph all of whose vertices have the same degree d. Show that there are at least d distinct perfect matchings in G Let G be a bipartite graph all of whose vertices have the same degree d. Show that
there are at least d distinct perfect matchings in G. (Two perfect matchings M1 and
M2 are distinct if M1 does not equal to M2 as sets.)
I am probably not understanding the definition of distinct perfect matching correctly. For example, if we have a regular bipartite graph with d = 2 like the one below:

It says M1 and M2 are different if they are different "as sets". Say we are looking at the perfect matching of X, or does it mean sets of edges or sets of vertices?
If it's sets of vertices, it can be {Y1, Y2}, {Y2, Y3} and {Y1, Y2, Y3}.
If it's sets of edges there are apparently 2 x 2 x 2 = 6 different sets.
And besides these, I have no clue how to attack this problem anyway, regardless of what it meant by "sets"...
I thought the answer would be d^(d/2) which is way off and absolutely wrong...
Help with intuitive explanation and steps are appreciated!!!

Hint:


*

*It is trivial for $d = 1$.

*For $d > 1$, remove edges of any perfect matching to get $(d-1)$-regular bipartite graph with $(d-1)$ distinct perfect matchings.


Good luck!
