Contractible edges in 5-connected graphs

Problem: Is there an integer k such that every 5-connected graph of order at least k contains a nonempty set of at most k edges such that the graph obtained by contracting these edges (and removing resulting parallel edges and loops) is 5-connected?

My student Gašper Fijavž [1] conjectured that k = 5 works for all but finitely many graphs (all of which have at most 12 vertices). See also [2].

A similar question for connectivity larger than 5 has negative answer, and has positive answer for connectivities less than 5.


[1] G. Fijavž, Ph. D. Thesis and a talk at the Bled 2001 Conference.

[2] M. Kriesell, Contractible edges in graphs of a given vertex connectivity, manuscript, 2001.

Send comments to

Revised: oktober 29, 2001.