# Perfect matching in $r$-connected graph

$G$ is a simple $r$-connected ($r \geq 1$) graph, with even number of vertices. Assume that $G$ doesn't contain $K_{1,r+1}$ as an induced subgraph. Prove that $G$ has a perfect matching.

Now, I can see why it's true without the condition on $K_{1,r+1}$: obviously, $\delta(G) \geq r$, and then, by using Tutte's theorem in a fashion of a proof of Petersen theorem ($ro(V[G-S]) \leq \sum{M_i} \leq \sum_{v \in S}d(v) \leq r|S|$, when $M_i$ is number of edges between $S$ and a component $C_i$), I'm getting to what I was needed to prove.

Am I missing something?

Thanks.

• What happens when you try and run through your argument on $K_{r,r+2}$? – Kevin P. Costello Aug 16 '12 at 19:56
• I'm not sure... What is the $S$ I need to take for the argument to fail? – Pavel Aug 17 '12 at 6:02
• If you remove the $r$ vertices on the smaller side, you leave $r+2$ odd components. – Kevin P. Costello Aug 17 '12 at 8:51
• Oh, right. So it's a precondition for not getting too many (odd) components. Seems like, though, in that case, it doesn't require any additional proof? – Pavel Aug 17 '12 at 9:57

Yes the mistake is that you'll need, for each odd component $C$ with neighbours $N'(C)$ in $S$, to allow counting at most one edge for a vertex in $N'(C)$ (i.e. you'll count a smaller set of edges such that no two vertices in the same component are sharing the same vertex in $S$) that's the only way to be able to make the last inequality.