# Any $r$-connected graph with certain properties must contain a perfect matching

Let there be $G$ an $r$-connected simple graph for $r \geq 1$ with an even number of vertices, we also know that $K_{1,r+1}$ is not a subgraph of $G$, I need to show that $G$ contains a perfect matching.

My initial approach was attempting to use a similiar method to the proof of Tutte's theorem then for any set of vertices less than $r$ the condition holds trivially. For a subset of vertices $S$ s.t. $|S|>r$ I wanted to somehow show that if $o(G\setminus S)>|S|$ then there has to be a $K_{1,r+1}$ subgraph.

• $o(G\setminus S)$ in this context means the number of odd connectivity components of $G\setminus S$
• $K_{1,r+1}$ is the $r+1$ edges star graph.

Would appreciate some hints.

• Really, an "$r$ minus $c$ times $o$ times $n$ times $n$ times $e$ times $c$ times $t$ times $e$ times $d$" graph? Or did you mean an "$r$-connected" graph? (But seriously, math mode is for math. Use *italics* to make italics.) – Zev Chonoles Feb 13 '14 at 5:56

Since $G$ has no $K_{1,r+1}$ then the degree $d(v) \le r$ for any vertex v. Also, since $G$ is $r$-connected, then $G$ is at least $r$-edge-connected graph and $d(v) \ge r$ for any vertex v. Hence, $G$ is $r$-regular $r$-edge-connected graph.
For $S \subset V(G)$, let $G_1, G_2, \cdots G_k$ be the odd components of $G \setminus S$.Let $m_i$ be the number of edges between $G_i$ and $S$.By edge connectivity of $G$, we have $m_i \ge r$ which means $\frac{m_i}{r} \ge 1$.
Notice that $\sum_{i=1}^{k}m_i \le r|S|$ i.e. the total number of edges between the $G_i$ and $S$ is less than the total number of edges that could possibly come from $S$ ( $r|S|$ since $G$ is $r$-regular.)
In an other word, $|S| \ge \frac{1}{r}\sum_{i=1}^{k}m_i = \sum_{i=1}^{k}\frac{m_i}{r} \ge k = o(G \setminus S)$, thus by Tutte's theorem $G$ has a perfect matching.