Fan-type conditions for collapsible graphs (Q2713638)

Let \(O(H)\) be the set of all vertices of odd degree in a graph \(H\). A graph \(G\) is collapsible if for every even set \(X\subseteq V(G)\) there exists a connected spanning subgraph \(H_X\) of \(G\) such that \(O(H_X)=X\). It is said that \(G\) satisfies a Fan-type condition if for every pair of vertices \(u,v\) with \(\operatorname {dist} (u,v)=2\) in \(G\) NEWLINE\[NEWLINE \max \{ d(u),d(v)\} \geq \frac {n}{(g-2)p}-\varepsilon,NEWLINE\]NEWLINE where \(g\in \{ 3,4\} \) is the girth of \(G\) and \(p\geq 2\) and \(\varepsilon >0\) are fixed numbers. The simple 2-edge-connected collapsible graphs for \((g,p,\varepsilon)=(3,2,2)\) and \((4,2,1/2)\) and the simple 3-edge-connected collapsible graphs for \((g,p,\varepsilon)=(3,4,9/4),(4,4,9/4)\) and \((4,4,5/8)\) are characterized.