Collapsible graph

Collapsible graph — разборный граф, складной граф.

1. A cf-graph $\,G$ is called a collapsible one if it can be transformed to a trivial one upon repeated application of transformations $\,T_{1}$ and $\,T_{2}$ desribed below.

Let $\,(n,n)$ be an arc of $\,G$ . The transformation $\,T_{1}$ is removal of this edge.

Let $\,n_{2}$ not be the initial node and have a single predecessor, $\,n_{1}$ . The transformation $\,T_{2}$ is the replacement of $\,n_{1}$ , $\,n_{2}$ and $\,(n_{1},n_{2})$ by a single node $\,n$ . The predecessors of $\,n_{1}$ become the predecessors of $\,n$ . The successors of $\,n_{1}$ or $\,n_{2}$ become the successors of $\,n$ . There is an arc $\,(n,n)$ if and only if there was formerly an edge $\,(n_{2},n_{1})$ or $\,(n_{1},n_{1})$ .

2. A graph $\,H$ is called collapsible if for every even subset $\,S \subseteq V(H)$ , there is a subgraph $\,T$ of $\,H$ such that $\,H - E(T)$ is connected and the set of odd degree vertices of $\,T$ is $\,S$ .