Use a greedy ear decomposition to prove that every 2-connected claw-free graph G has [n(G)/3]

141 Views Asked by At

This question from problem of chapter of Introduction to Graph Theory

A greedy ear decomposition of a 2-connected graph is an ear decomposition that begins with a longest cycle and iteratively adds a longest possible ear. Use a greedy ear decomposition to prove that every 2-connected claw-free graph G has [n(G)/3] pairwise-disjoint copies of P3 [Kaneko–Kelmans–Nishimura[2000]).

I try to draw some simple but I still can't to finish it. The results that I got. Let C be the longest cycle of C.If xy,xz are two edges of C and w is a vertex of not in C have xw is an edge,then yz must be an edge, otherwise wx or wy is an edge by G is claw-free,then we can find a cycle longer than C.