Menu
Let \(G\) be a simple connected graph on \(2n\) vertices with a perfect matching. \(G\) is \(k\)-\({extendable}\) if for any set \(M\) of \(k\) independent edges, there exists a perfect matching in \(G\) containing all the edges of \(M\). \(G\) is \({minimally \; k-extendable}\) if \(G\) is \(k\)-extendable but \(G – uv\) is not \(k\)-extendable for every pair of adjacent vertices \(u\) and \(v\) of \(G\). The problem that arises is that of characterizing \(k\)-extendable and minimally \(k\)-extendable graphs. The first of these problems has been considered by several authors whilst the latter has only been recently studied. In a recent paper, we established several properties of minimally \(k\)-extendable graphs as well as a complete characterization of minimally \((n – 1)\)-extendable graphs on \(2n\) vertices. In this paper, we focus on characterizing minimally \((n – 2)\)-extendable graphs. A complete characterization of \((n – 2)\)-extendable and minimally \((n – 2)\)-extendable graphs on \(2n\) vertices is established.