A Theorem on \(n\)-Extendable Graphs

Tsuyoshi Nishimura1
1 Department of Mathematics Shibaura Institute of Technology Fukasaku, Omiya 330 Japan

Abstract

A graph \(G\) having a \(1\)-factor is called \(n\)-extendable if every matching of size \(n\) extends to a 1-factor. We show that
if \(G\) is a connected graph of order \(2p (p \geq 3)\), and g and n are integers, \(1 \leq n < q < p\), such that every induced connected subgraph of order \(2q\) is \(n\)-extendable, then \(G\) is n-extendable.