| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4648136 | Discrete Mathematics | 2012 | 8 Pages |
A removable edge in a 3-connected cubic graph GG is an edge e=uve=uv such that the cubic graph obtained from G∖{u,v}G∖{u,v} by adding an edge between the two neighbours of uu distinct from vv and an edge between the two neighbours of vv distinct from uu 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.
