On removable edges in 3-connected cubic graphs

A removable edge in a 3-connected cubic graph G is an edge e = u v such that the cubic graph obtained from G ∖ { u , v } by adding an edge between the two neighbours of u distinct from v and an edge between the two neighbours of v distinct from u is still 3-connected. Li and Wu (2003) [5] showed that a spanning tree in a 3-connected cubic graph avoids at least two removable edges, and Kang et al. (2007) [3] showed that a spanning tree contains at least two removable edges. We show here how to obtain these results easily from the structure of the sets of non removable edges and we give a characterization of the extremal graphs for these two results. We investigate a neighbouring problem by considering perfect matchings in place of spanning trees.