Prove that if $G$ is an $r$-regular, $(r-2)$-edge-connected graph of even order containing at most $r-1$ distinct edge cuts then $G$ has a $1$-factor Prove that if $G$ is an $r$-regular, $(r-2)$-edge-connected graph $(r>3)$ of even order containing at most $r-1$ distinct edge cuts of cardinality $r-2$ then $G$ has a $1$-factor


Tutte's theorem: A non trivial graph $G$ has a $1$-factor if and only if $k_0 (G-S) \leq |S|$ for every proper subset $S$ of $V(G)$


I'm not sure if I understand this correctly, but here is what I thought. I want to use the Tutte's theorem to prove this (maybe there is a better way) 
Let $G_i$ and $H_i$ be the odd and even components of $G$ respectively and $S$ be a subset of $V(G)$ then 
$\sum |V(G_i)| + \sum  |V(H_i)| +|S|=n=2k$
$G$ is $(r-2)$-edge-connected, so can't I conclude that $|S|=r-2$ or $|S|=r-1$? I'm not sure I understand this phrase "containing at most $r-1$ distinct edge cuts of cardinality $r-2$"
I want to prove that $G$ has a $1$-factor so I can't say that in every odd component, there must be one vertex that is adjacent to a vertex in $S$, can I?
I know that, if a graph has a $1$-factor, then it has a perfect matching. Is it safe to say if a graph has a perfect matching then it has a $1$-factor?
 A: Assume for sake of contradiction that $G$ does not have a perfect matching.  By Tutte's theorem, there exists a set $S$ such that $G - S$ has more odd components than there are vertices in $S$.  Let $A_1, \ldots, A_t$ be the odd components of $G - S$.  Notice that $t + |S|$ is even, since $G$ has an even number of vertices, and therefore $|S| < t$ implies $|S| + 2 \leq t$.  
Notice that it is impossible that there are exactly $r-1$ edges between $S$ and one of the $A_i$.  This is because the degree sum of the subgraph induced by $A_i$ would then be $r|A_i| - (r - 1)$ which is an odd number, and by the famous handshake lemma we can't have an odd degree sum.  
The number of edges between $S$ and $A_i$ is at least $r-2$, since $G$ is $r-2$ edge connected.  At most $r-1$ of the $A_i$ have $r-2$ edges to $S$.  As discussed in the previous paragraph, the other $(t - (r-1))$ components must have at least $r$ edges to $S$.
So how many edges are there leaving $S$?  Well on the one hand this is at most $r |S| \leq r(t - 2) = rt - 2r$, since the vertices each have degree $r$.  On the other hand, this is at least (counting by how many edges are between $S$ and each $A_i$) the following: $(r-2)(r-1) + r(t - (r-1)) = rt- 2r + 2$.  Thus we have a contradiction which proves the result.
A: Here are some hints and answers for you:  first off, perfect matching and $1$-factor are synonyms, and can be used interchangeably.
I don't think we can conclude $|S| = r-2$ or $r-1$, unless I'm missing some suppositions in your thinking.  $S$ can be any size.
But you're right, I think Tutte's theorem is the key to proving this.  Tutte's theorem can be tricky to think about -- I'd recommend doing some specific examples.  For example:
This graph does not have a matching, because $|S| = 3$ is smaller than the number of odd components of $G - S$ which is $5$.  However, this fails to be a counter example since there are so many edge cuts of size $2$ (in particular, there are $5$ distinct edge cuts of size two, the edges between $S$ and each of the odd components).    
