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 | 3 ) time.