Removable and forced subgraphs of graphs.

A connected graph G is H - removable if H is a subgraph of G , G has at least | V (H) | + 2 vertices and G − V (H ′) has a perfect matching for every subgraph H ′ of G isomorphic to H. So a connected graph is k K 2 -removable if and only if it is k -extendable, where k K 2 is a matching of size k. Further G is an H - forced graph if G − V (H ′) has a unique perfect matching for every subgraph H ′ of G isomorphic to H. In this paper, we first characterize k K 2 -forced graphs for k ≥ 2 as K 2 k + 2 and K k + 1 , k + 1 by using randomly matchable graphs. Let P i denote a path with i vertices. We show that P 3 - and P 4 -removable graphs are factor-critical and 1-extendable respectively. By using ear decomposition, we obtain that a connected graph G is P 3 -forced if and only if G is K 5 or C 2 k + 1 (k ≥ 2). Finally we prove that a connected graph G is P 4 -forced if and only if G is isomorphic to K 6 , K 3 , 3 , C 2 k (k ≥ 3), the Petersen graph, a uniform theta graph Θ 3 n (n ≥ 3) or C 12 +. [ABSTRACT FROM AUTHOR]