82.2k views
0 votes
Let G be a connected graph of even order. Prove that if G contains no induced subgraph isomorphic to K₁,₃, then G has a perfect matching

User Oderfla
by
8.0k points

1 Answer

5 votes

Final answer:

The conditions of the question imply that the connected graph adheres to Tutte's theorem, which ensures the presence of a perfect matching. This is because having no K₁,₃ subgraph means the graph is unlikely to form odd components with any vertex removal.

Step-by-step explanation:

A connected graph of even order without an induced subgraph isomorphic to K₁,₃ (a claw) is said to satisfy the conditions of Tutte's theorem for the existence of a perfect matching. The theorem asserts that a graph G has a perfect matching if and only if for every subset U of the graph's vertices, the graph G-U has at most |U| connected components with an odd number of vertices. Since a connected graph with no claw as an induced subgraph prohibits vertices with three independent neighbors, it tends to avoid creating components with an odd number of vertices when arbitrary sets of vertices are removed. Therefore, such a graph satisfies the condition of Tutte's theorem and thus has a perfect matching.

User Mononym
by
8.1k points