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.
References:
[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 Bojan.Mohar@uni-lj.si