## 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.

**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

##### Revised: oktober 29, 2001.