A new recursive theorem on \(n\)-extendibility (Q675894)

A graph \(G\) having a 1-factor is called \(n\)-extendible if every matching of size \(n\) extends to a 1-factor. A graph \(G\) is called \(\langle r,n\rangle\)-extendible if \(G-S\) is \(n\)-extendible for every connected subset \(S\) of order \(2r\) for which \(G-S\) is connected. Let \(p\), \(r\) and \(n\) be integers with \(r>0\) and \(p-r>n>0\). It is shown that every 2-connected \(\langle r,n\rangle\)-extendible graph of order \(2p\) is \(\langle r-1,n\rangle\)-extendible. This result is used to show that if \(G\) is a 2-connected graph of order \(2p\) and if \(r\geq 0\) and \(n>0\) are integers such that \(p-r\geq n+1\), and if \(G-S\) is \(n\)-extendible for every connected subgraph \(S\) of order \(2r\) for which \(G-S\) is connected, then \(G\) is \(n\)-extendible.