Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A short proof of a theorem of Kano and Yu on factors in regular graphs. | A short proof of a theorem of Kano and Yu on factors in regular graphs Lutz Volkmann Lehrstuhl II fiir Mathematik RWTH Aachen University 52056 Aachen Germany e-mail volkm@ Submitted Jul 13 2006 Accepted Jun 1 2007 Published Jun 14 2007 Mathematics Subject Classification 05C70 Abstract In this note we present a short proof of the following result which is a slight extension of a nice 2005 theorem by Kano and Yu. Let e be an edge of an r-regular graph G. If G has a 1-factor containing e and a 1-factor avoiding e then G has a k-factor containing e and a k-factor avoiding e for every k 2 1 2 . r 1g. Keywords Regular graph Regular factor 1-factor k-factor. We consider finite and undirected graphs with vertex set V G and edge set E G where multiple edges and loops are admissible. A graph is called r-regular if every vertex has degree r. A k-factor F of a graph G is a spanning subgraph of G such that every vertex has degree k in F. A classical theorem of Petersen 3 says Theorem 1 Petersen 3 1891 Every 2p-regular graph can be decomposed into p disjoint 2-factors. Theorem 2 Katerinis 2 1985 Let p q r be three odd integers such that p q r. If a graph has a p-factor and an r-factor then it has a q-factor. Using Theorems 1 and 2 Katerinis 2 could prove the next attractive result easily. Corollary 1 Katerinis 2 1985 Let G be an r-regular graph. If G has a 1-factor then G has a k-factor for every k 2 1 2 . rg. Proofs of Theorems 1 and 2 as well as of Corollary 1 can also be found in 4 . The next result is also a simple consequence of Theorems 1 and 2. Theorem 3 Let e be an edge of an r-regular graph G with r 2. If G has a 1-factor THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 N10 1 containing e and a 1-factor avoiding e then G has a k-factor containing e and a k-factor avoiding e for every k 2 1 2 . r 1g. Proof. Let F and Fe be two 1-factors of G containing e and avoiding e respectively. Case 1 Assume that r 2m 1 is odd. According to Theorem 1 the .