On n-extendable graphs

AbstractA graph G is said to be n-extendable if it is connected, has a set of n independent lines and every set of n independent lines in G extends to (i.e. is a subset of) a perfect matching of G. Nearly all n-extendable graphs (n⩾2) are shown to be (n–1)-extendable and (n + 1)- connected. The special cases of 2- and 3-extendable graphs and their relationships with bicritical and elementary bipartite graphs are then studied