Undirected connected claw-free graph with even number of vertices implies existing perfect matching

I need to prove that graph $G$ which:

• is undirected
• is connected
• has an even number of vertices
• is claw-free (does not contain $K_{1,3}$ as an induced subgraph)

implies $G$ has a perfect matching.

I've come up with some solution decomposing the graph and applying Tutte's theorem but it turned out to be incorrect. I'm now completely stuck not able to move forward and the materials I found did not really help me generate the proof idea. It would be of great help just to get a hint how to think.

It relates to this question Proving that every connected graph of order 4 that is not $K_{1,3}$ has a perfect matching. but nobody answered part "b" which is essentially what I'm asking.

Links to materials can be found on https://en.wikipedia.org/wiki/Claw-free_graph in section about matching however the explanations on wiki and elsewhere were not enough to connect it.

Solution 1:

I will try to give a short proof using D.Sumner's considerations.

Let $G$ be a connected claw-free graph of even order. Then graph $G$ has a perfect matching.

If the order of $G$ is $2$, then this statement is obviously true. Let $|G|>2$. We prove first that there exist adjacent vertices $x,y$ such that the graph $G-\{x,y\}$ is connected.

After that our assertion can be proved by induction on the order of graph $G$.

Let $a_1,\ldots, a_s,x,y$ be the longest path in $G$ in which vertices do not repeat. Then $s\geq1$. Consider the graph $H=G-\{x,y\}$. Let $A$ be the component of graph $H$ containing vertex $a_1$. The vertex $y$ is not adjacent to any vertex of $H-A$ (otherwise we can lengthen our path).

Let $H-A\neq\varnothing$ and let $b$ be a vertex from $H-A$ adjacent to $x$ (there is such a vertex otherwise $G$ is not connected). Then $b$ is isolated in $H-A$ (otherwise we get a longer path in $G$). It follows that if $H-A$ contains another vertex $c$ then $x,y,b,c$ is a claw. Hence $H-A=\{b\}$. But then the vertices $y$ and $a_s$ are adjacent (otherwise $x,y,b,a_s$ is a claw). In this case we obtain that the graph $G-\{x,b\}$ is connected. The proof is finished.