On Edge Contractible Graphs

Abstract

Let $G$ be a connected graph with a perfect matching on $2n$ vertices ($n\ge 2$). A graph $G^{\prime }$ 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^{\prime }$ of $G$ with $|V(G^{\prime })|$ even, $G^{\prime }$ has a perfect matching. In this note, we obtain a sufficient and necessary condition for a graph to be an edge contractible graph.