I've been asked to prove that any graph $G$ which is $n$-connected, $n$-regular, and has even order has a one-factor.
A hint that we were given for proving this was a corollary to Tutte's theorem, which states that;
If the graph of multigraph $G$ has an even number of vertices, then $G$ has no one-factor if and only if there is some $w$-set $W$ of vertices such that $G-W$ has at least $w+2$ odd components
However, I'm having a lot of trouble actually applying this to the question. I know that I have to use both the connectivity and regularity of the graph to say something about what components we get after removing a certain number of vertices, but I'm really just not confident in applying these two conditions.
I've tried to start a proof by contradiction to the above corollary, but I'm not sure if I'm even doing it correctly.
Firstly, we start with some graph $G$ of even order. We also note that, due to the connectivity of $G$, we must remove at least $n$ vertices to disconnect it into some number of components. So, this means that there exists some $n$-set $W$ of vertices such that $G-W$ has at least $n+2$ odd components.
At this point, I thought it was best to consider the cases in which $n$ was even, and $n$ was odd. If $n$ is even, then we need to remove an even number of vertices to disconnect $G$, which means that the order of $G-W$ would be even. But, at this stage, I'm not sure how to appeal to the connectivity of the graph to say anything of relevance. I'd like to say that, if we've got an even number of vertices, then we've got either an even number of even components, or an even number of odd components, but I'm just not sure.
In a similar way, if we delete an odd number of vertices from $G$, then we necessarily have an odd number of vertices left over, which would imply at least one odd component, but again, I'm not sure how to relate this back to the regularity of the graph, or the corollary itself.
If anyone could provide me with some insight into this, I'd be over the moon. This question is really stressing me out ;-;
It's perhaps easier to state Tutte's theorem as follows, which is how I mostly see it anyways.
Tutte's Theorem: Let $G(V,E)$ be a graph. Then $G$ has a perfect matching if and only if for every subset $W\subseteq V$ of vertices, the subgraph induced by $V\backslash W$ has at most $|W|$ odd components. $\square$
It's a simple exercise to prove that these two versions are equivalent; your version is just the negation of mine. Also note that there's no real need to consider multigraphs when finding perfect matchings as a multigraph will have a perfect matching if and only if its underlying simple graph has a perfect matching.
Now onto the proof of the corollary.
Corollary: Let $G(V,E)$ be a $n$-regular and $n$-connected graph. Then $G$ has a perfect matching.
Proof: Let $W\subseteq V$ be an arbitrary subset of the vertices of $G$. The graph induced by $V\backslash W$ contains even and odd components. Remove from $G$ (the original graph) all vertices belonging to the even components and collapse all vertices of each odd component to a single vertex $u_i$. Call the collection of such vertices $U$. Note that $|U|$ is precisely the number of odd components induced by $V\backslash W$.
Remove all multi-edges and loops from the resulting graph and remove all the edges internal to $W$. Note that what remains is a bipartite graph $\tilde{G}$ with vertex bipartition $(W,U)$.
Finally, note that $\deg(u_i) \ge n$ by the $n$-connectivity assumption while $\deg(w_i) \le n$ by the regularity assumption. Summing the degrees over the bipartition of $\tilde{G}$, we have $$n|U|\le\sum_{u_i\in U}\deg(u_i)=\sum_{w_i\in W} \deg(w_i) \le n|W|$$ Therefore we conclude that $|U| \le |W|$. Since each vertex of $U$ represents an odd component, we conclude that the number of odd components induced by $V\backslash W$ is at most $|W|$. Since $W$ was arbitrary, this means that $G$ satisfies the hypotheses of Tutte's theorem and we have a perfect matching, as needed. $\square$