$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.
Best Answer
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.
And, in jumping to the last inequality you'll now need to use the special bipartite-free condition (this is a generalization of Petersen's theorem).