1-factor in r-connected graph

Question

I have this problem in graph theory: Let G be an r-connected graph of even order having no $K_{1,r+1}$ as an induced subgraph, for some r ≥ 1. Prove that G has a 1-factor.

So there are two directions I've been thinking of:

1. Induction on the number of vertices. the base is when |V(G)| = 2 and then its just 2 vertices connected with one edge between them and it is a 1-factor. The problem is in the induction step - assume we have a r-connected graph on k+2 vertices. I'd like to take out 2 of the vertices and use the induction hypothesis but how do I know I didn't damage the r-connectivity? I thought maybe to prove that every graph of even order can't be 2-connected because it has no $K_{1,r+1}$ as an induced subgraph but I wasn't able to do that and I started doubting if its true..

2. Usage of Tutte - a graph has a perfect matching if and only if for every S $\subseteq$ V, o(G-S) $\leq$ |S|. so if |S| < r, the graph is still connected and o(G-S) = 0 < |S|. but if not, how can I know anything about o(G-S)?

I would really appreciate any kind of help, even just to know which of the ways are closer to the solution...if I'm anywhere near it anyway. thank you :)

Answer 1

Use Tutte's theorem. Argue that for every $S \subseteq V$ for which $G-S$ is not connected,

1. Every component of $G-S$ (even or odd) has edges to at least $r$ vertices in $S$.
2. Every vertex of $S$ has edges to at most $r$ different components of $G-S$.

Conclude that $G-S$ has at most $|S|$ components.

The even order of $G$ is used only in the special case $S = \varnothing$.