Collapsible graph

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

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

Let [math]\displaystyle{ (n,n) }[/math] be an arc of [math]\displaystyle{ G }[/math]. The transformation [math]\displaystyle{ T_{1} }[/math] is removal of this edge.

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

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