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?
Best Answer
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.