Proving that every connected graph of order 4 that is not $K_{1,3}$ has a perfect matching.

Question

I am asked to prove two things:

(a) Prove that every connected graph of order 4 that is not $K_{1,3}$ has a perfect matching.

(b) Let G be a connected graph of even order. Prove that if G contains no induced subgraph isomorphic to $K_{1,3}$, then G has a perfect matching.

Now, I think that proving part a might help a lot with part b but I am not too sure how to approach this. I have seen a solution around mentioning something about claws but I have not learned that so I do not get it. I do see I would need to find a set that contains 2 edges to have a perfect matching since the order is 4 but I am not sure how to continue. Any suggestions?

Answer 1

Assume for a contradiction that $G$ is a connected graph of order $4$ which is not $K_{1,3}$ and has no perfect matching.

$G$ is a spanning subgraph of the graph $K_4,$ which has a proper edge-coloring with $3$ colors. Since $G$ has no perfect matching, it has at most one edge of each color; therefore, $G$ has at most $3$ edges.

Since $G$ is connected of order $4,$ it has at least $3$ edges. Therefore $G$ is a tree and has exactly $3$ edges.

Plainly, $G$ has no vertex of degree greater than $3.$ Moreover, since $G$ is not $K_{1,3},$ it has no vertex of degree $3.$ Therefore $G$ has maximum degree at most $2.$

A tree with maximum degree $\le2$ is a path. Therefore $G=P_4.$ But $P_4,$ a path of even order, has a perfect matching. This contradicts our assumption that $G$ has no perfect matching.

Answer 2

A $3$-edge path has a perfect matching (shown in red):

A connected $4$-vertex graph has a spanning tree: either $K_{1,3}$ or a $3$-edge path (as there are no other $4$-vertex trees).

If we add an edge to $K_{1,3}$, we get a $3$-edge-path subgraph (and thus a perfect matching):

Thus, except for $K_{1,3}$, any connected $4$-vertex graph has a $3$-edge subgraph, and thus a perfect matching.