Contractible edges in subgraphs of 2-connected graphs

Contractible edges in spanning trees, longest paths and maximum match-ings in 2-connected graphs non-isomorphic to K₃ are investigated. Every spanning tree and every longest path are shown to contain at least two contractible edges. All graphs with a spanning tree / a longest path containing exactly two contractible edges are characterized. Also, we prove that there always exists a longest path P which contains more than |E(P)|/2 contractible edges, and the bound is asymptotically op-timal. Every maximum matching must contain a contractible edge and those graphs with a maximum matching having exactly one contractible edge are characterized. Finally, it is shown that there always exists a maximum matching M that contains at least 2(|M| + 1)/3 contractible edges, and the bound is optimal.