Matching cutsets in graphs
Augustine Moshi · Journal of Graph Theory · 1989
Abstract 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.