On 3-connected graphs with contractible edge covers of size \(k\) (Q1197021): Difference between revisions

It is well known [\textit{W. T. Tutte}, A theory of 3-connected graphs, Nederl. Akad. Wet., Proc., Ser. A 64, 441-455 (1961; Zbl 0101.409)] that every 3-connected, finite graph with at least 5 vertices has a contractible edge, i.e., an edge the contraction of which does not distroy the 3-connectivity. The distribution of these contractible edges had been considered in several papers. The authors now study 3-connected, finite graphs, where the contractible edges can be covered by \(k\) vertices, extending former results for \(k=2\) and \(k=3\). A typical result is the following theorem. Let \(K \subseteq V(G)\) with \(| K | \geq 3\) cover all contractible edges of a 3-connected, finite graph \(G\). Then \(G-K\) has at most \(| K |-2\) components of order at least 2, which are not triangles consisting of vertices of degree 3.