Matching cutsets in graphs

Let G = (V,E) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of F are incident with the same point, and G-F has more components than G. Chv?atal [2] proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs with maximum degree 4. We prove the following: (a) Every connected graph with maximum degree ?3 and on more than 7 points has a matching cutset. (In particular, there are precisely two connected cubic graphs without a matching cutset). (b) Line graphs with a matching cutset can be recognized in O(|E|) time. (c) Graphs without a chordless circuit of length 5 or more that have a matching cutset can be recognized in O(|V||E|³) time.