Proximity thresholds for matching extension in planar and projective planar triangulations

A graph on at least 2( m + 1) vertices with a perfect matching is said to be m ‐extendable if, given any matching M with | M | = m , there is a perfect matching F in G such that M ⊆ F . It has been known for some time that no planar graph is 3‐extendable. More recently, a graph on at least 2 m + 2 vertices has been defined to be distance d m ‐extendable if given any matching M with | M | = m in which the edges lie at pair‐wise distance at least d , there is a perfect matching containing M . In another recent article it was shown that a 5‐connected even planar triangulation is distance 2 3‐extendable, but not necessarily distance 2 4‐extendable. Moreover, it has also been shown that such a graph need not be distance 3 10‐extendable. Hence it is of interest to know the largest integer m such that distance d m ‐extendable holds for all such graphs. The above tells us that for d = 2, the maximum value is m = 3. In the present work, it is shown that for d = 5, in fact, there is no upper bound on m such that a 5‐connected, even planar, or projective planar, graph G on at least 2 m + 2 vertices is distance 5 m ‐extendable. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 38‐46, 2011