On Edge Contractible Graphs

Hong Lin1, Lin Yu1
1School of Sciences, Jimei University, Xiamen 361021, P. R. China

Abstract

Let \(G\) be a connected graph with a perfect matching on \(2n\) vertices (\(n \geq 2\)). A graph \(G’\) is a contraction of \(G\) if it can be obtained from \(G\) by a sequence of edge contractions. Then \(G\) is said to be edge contractible if for any contraction \(G’\) of \(G\) with \(|V(G’)|\) even, \(G’\) has a perfect matching. In this note, we obtain a sufficient and necessary condition for a graph to be an edge contractible graph.