https://hal.inria.fr/inria-00516060Fouquet, Jean-LucJean-LucFouquetLIFO - Laboratoire d'Informatique Fondamentale d'Orléans - UO - Université d'Orléans - Ecole Nationale Supérieure d'Ingénieurs de BourgesThuillier, HenriHenriThuillierLIFO - Laboratoire d'Informatique Fondamentale d'Orléans - UO - Université d'Orléans - Ecole Nationale Supérieure d'Ingénieurs de BourgesOn removable edges in 3-connected cubic graphsHAL CCSD2012[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]Thuillier, Henri2010-09-08 16:09:282022-06-25 10:11:242010-09-08 16:21:28enJournal articleshttps://hal.inria.fr/inria-00516060/document10.1016/j.disc.2011.11.025application/pdf1A removable edge in a 3-connected cubic graph G is an edge e=uv 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 disctinct from u is still 3-connected. Li and Wu [1] showed that a spanning tree in a 3-connected cubic graph avoids at least two removable edges, and Kang, Li and Wu [2] 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. [1] WU Jichang and LI Xueliang, Removable edges outside a spanning tree of a 3-connected 3-regular graph, Journal of Mathematical Study, 36(3), 2003, 223-229. [2] KANG Haiyan, WU Jichang and LI Guojun, Removable edges of a spanning tree in 3-connected 3-regular graphs, LNCS, 4613, 2007, 337-345.