Every ${K}_{1, 3}$-free connected graph of even order has a perfect matching.
Probably it can be shown using the Tutte theorem about perfect matching.
Every ${K}_{1, 3}$-free connected graph of even order has a perfect matching.
Probably it can be shown using the Tutte theorem about perfect matching.
We want to prove that if $G$ has no perfect matching, then it contains the claw. Suppose $G$ has no perfect matching. A strengthening of Tutte's theorem, the Gallai-Edmonds theorem, allows us to take $S \subset G$ such that:
We will induct on the order of $S$.
If $|S| = 1$, then $o(G \setminus S) \ge 3$, since $o(G \setminus S) > |S|$ and $o(G \setminus S)$ must be odd since $|G|$ is even. There is an edge from $v \in S$ to all $3$ components, thus providing an example of the claw.
Now suppose $|S| = n+1$ and that the statement holds for $n$. Select $v_1 \in S$ adjacent to exactly two odd components $C_1$ and $C_2$. If it is adjacent to $3$, then we have an example of a claw. $G$ is connected, so we may find $v_2$ with an edge to one of $C_1$ and $C_2$ (let $v_2 c$ be an edge, with $c \in C_1$, without loss of generality).
Now, let $S^* = S - v_1$. We will show that $S^*$ satisfies our induction hypothesis: