Every ${K}_{1, 3}$-free connected graph of even order has a 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.

Solutions Collecting From Web of "Every ${K}_{1, 3}$-free connected graph of even order has a 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:

  • $o(G \setminus S) – |S|$ be maximal and
  • $S$ is matchable to the components of $G \setminus S$.

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:

  • $o(G \setminus S^*) – |S^*|$ is still maximal: $C_1 \cup \{ v_1 \} \cup C_2$ is an odd component of $G \setminus S^*$ and all other components are preserved.
  • Moreover, $S^*$ is still matchable to $G \setminus S^*$, since $v_2 c \in E$.