let g be a graph with vertex set v(g ) and edge set e(g ) .
the number of vertices of a graph g is the order of g and is denoted by n. on the other hand , the number of edges of g is the size of g and is denoted by e. we denote the degree of vertex v in g by dg(v ) . for two subsets s , tv(g ) , let eg(s , t ) denote the number of edges of g joining s to t. let c(g ) and co(g ) denote the number of components and the number of odd components of g , respectively .
a k - factor of a graph g is a spanning subgraph h of g such that dh(x)=k for every xv(g ) .
let d and s be disjoint subsets of v(g ) and c be a component of g(ds ) .
c is a k - odd component of g(ds ) if k|c|+eg(s , v(c ) ) is odd .
petersen obtained the following theorem , which is chronologically the first result on k - factors in regular graphs .
theorem  1.1petersen  every  3-regular ,  2-connected graph has a  1-factor .
every  3-regular ,  2-connected graph has a  1-factor . for the existence of 1-factors in arbitrary graphs ,
theorem  1.2tutte  a graph 
 g 
 has a  1-factor if and only if 
 co(gs)|s| 
 for all 
 sv(g ) .
a graph 
 g 
 has a  1-factor if and only if 
 co(gs)|s| 
 for all 
 sv(g ) .
a graph 
 g 
 has a 
 k - factor if and only if , for all 
 d , sv(g ) 
 with 
 ds=0,g(d , s)=k|d|+xsdg(x)k|s|eg(d , s)qg(d , s;k)0,where 
 qg(d , s;k ) 
 is the number of 
 k - odd components 
 c 
 of 
 g(ds ) 
 .
a graph 
 g 
 has a 
 k - factor if and only if , for all 
 d , sv(g ) 
 with 
 ds=0,g(d , s)=k|d|+xsdg(x)k|s|eg(d , s)qg(d , s;k)0,where 
 qg(d , s;k ) 
 is the number of 
 k - odd components 
 c 
 of 
 g(ds ) 
 .
the following theorem examines the existence of a 1-factor in vertex - deleted subgraphs of a regular graph .
let 
 g 
 be a 
 2r - regular , 
 2r - edge - connected graph of odd order .
for any vertex 
 u 
 in 
 g , then graph 
 gu 
 has a  1-factor .
let 
 g 
 be a 
 2r - regular , 
 2r - edge - connected graph of odd order .
for any vertex 
 u 
 in 
 g , then graph 
 gu 
 has a  1-factor .
theorem  1.5katerinis  let 
 g 
 be a 
 2r - regular , 
 2r - edge - connected graph of odd order .
if 
 m 
 is an integer such that 
 1mr , then 
 gu 
 has an 
 m - factor for any vertex 
 uv(g ) .
let 
 g 
 be a 
 2r - regular , 
 2r - edge - connected graph of odd order .
if 
 m 
 is an integer such that 
 1mr , then 
 gu 
 has an 
 m - factor for any vertex 
 uv(g ) . in this paper , we set independent values to the degree and the edge - connectivity .
theorem  1.6let 
 m 
 and 
 r 
 be two integers such that 
 2mr 
 .
let 
 g 
 be a 
 2r - regular , 
 2m - edge - connected graph with odd order .
if one of the following conditions holds , then 
 gv 
 has a 
 k - factor for all 
 vv(g).(i)k 
 is even and 
 2km 
 ; ( ii)k 
 is odd , 
 3km 
 and 
 2m >
r . let 
 m 
 and 
 r 
 be two integers such that 
 2mr 
 .
let 
 g 
 be a 
 2r - regular , 
 2m - edge - connected graph with odd order .
if one of the following conditions holds , then 
 gv 
 has a 
 k - factor for all 
 vv(g).(i)k 
 is even and 
 2km 
 ; ( ii)k 
 is odd , 
 3km 
 and 
 2m >
k 
 is even and 
 2km 
 ; k 
 is odd , 
 3km 
 and 
 2m >
our results reveal an interesting behavior of a k - factor with respect to the parity of k and a difference between the case k=1 and k>1 .
in this section , we give the proof of theorem  1.6 and show that each hypothesis can not be weakened .
let h = gu . by theorem  1.3 , there exist disjoint subsets d and s of v(g)u such that ( 1)qh(d , s;k)+xs(kdhd(x))k|d|+2
so k|s|k|d|+2 and hence |s|>|d| . since v(h)=ds and |v(h)| is even , therefore ( 3)|s||d|+2 . now
since g is 2r - regular , by tutte s theorem we have xs(2rdgd(x))2r|d| , which implies 2r|s|xsdgd(x)2r|d| . therefore , 2r(|s|+1)xsdgd(x)2r|d| , and hence , ( 4)(2rk)|s|+k|s|+2rxsdgd(x)k|d|+(2rk)|d| .
also xsdgd(x)=xsdgd(x)+dgd(u)=xsdhd(x)+eg(u , s)+dgd(u ) . therefore ( 4 ) becomes ( 5)k|d|+(2rk)|d|(2rk)|s|+k|s|+2rxsdhd(x)eg(u , s)dgd(u ) . now using ( 2 ) and eg(u , s)dgd(u)2r , ( 5 ) implies ( 6)(2rk)(|s||d|)2r2 .
moreover , since |s||d|+2 by ( 3 ) , we can conclude from ( 6 ) that kr+1 . that is a contradiction ,
we conclude k|s|k|d|+1 , and hence |s|>|d|.since g is a 2m - edge - connected , 2r - regular graph , we have 2r|d|eg(d , v(gd))=eg(d , v(w))+eg(d , s)=eg(ds,v(w))eg(s,v(w))+eg(d , s)=eg(ds,v(w))(xsdgd(x)2eg(s,s))+(2r|s|xsdgd(x))=eg(ds,v(w))2xsdgd(x)+2eg(s,s)+2r|s|2m2(xsdhd(x)+eg(u , s)+dgd(u))+2eg(s,s)+2r|s|=2m2xsdhd(x)2dgd(u)+2eg(s , s)+2r|s|2m2xsdhd(x)+2r|s|2r . now
we have 2r|d|eg(ds,v(w))2xsdgd(x)+2eg(s,s)+2r|s|=eg(ds,v(w))2(xsdhd(x)+eg(u , s)+dgd(u))+2eg(s,s)+2r|s|=eg(ds,v(w))2xsdhd(x)2dgd(u)+2eg(s , s)+2r|s|2mc(w)2xsdhd(x)2r+2r|s|(since  g  is  2m - connected)(2m2)c(w)+(2r2k)|s|2r+2k|d|+4(by inequality ( 1))4m2r+(2r2k)|s|+2k|d| .
thus we have ( 2r2k)(|d||s|+1)2 m , from which it follows |d||s| . for every odd component c of w , the integer k|v(c)|+eh(v(c),s ) is odd .
since k is an even integer , eh(v(c),s ) must be odd . thus eh(v(c),s)1 and xsdhd(x)qh(d , s;k ) .
hence ( 1 ) implies k|s|k|d|+2 , from which it follows that |s||d|+1 , a contradiction.next assume condition ( ii ) of the hypothesis ; that is , k3 is odd and 2m > r .
, we have ( 9)|d||s|1k(qxsdhd(x)2 ) , and qk+2 since |d|>|s| . by ( 8) and ( 9 )
, there exist disjoint subsets d and s of v(g)u such that ( 1)qh(d , s;k)+xs(kdhd(x))k|d|+2 . define s=s{u } and w=(gd)s. claim  1c(w)2 .
so k|s|k|d|+2 and hence |s|>|d| . since v(h)=ds and |v(h)| is even , therefore ( 3)|s||d|+2 . now
since g is 2r - regular , by tutte s theorem we have xs(2rdgd(x))2r|d| , which implies 2r|s|xsdgd(x)2r|d| . therefore , 2r(|s|+1)xsdgd(x)2r|d| , and hence , ( 4)(2rk)|s|+k|s|+2rxsdgd(x)k|d|+(2rk)|d| .
therefore ( 4 ) becomes ( 5)k|d|+(2rk)|d|(2rk)|s|+k|s|+2rxsdhd(x)eg(u , s)dgd(u ) . now using ( 2 ) and eg(u , s)dgd(u)2r , ( 5 ) implies ( 6)(2rk)(|s||d|)2r2 .
moreover , since |s||d|+2 by ( 3 ) , we can conclude from ( 6 ) that kr+1 .
that is a contradiction , so case 1 can not occur . now qh(d , s;k)1 , and this implies ( 7)xs(kdhd(x))k|d|+1 .
we conclude k|s|k|d|+1 , and hence |s|>|d| . since g is a 2m - edge - connected , 2r - regular graph , we have 2r|d|eg(d , v(gd))=eg(d , v(w))+eg(d , s)=eg(ds,v(w))eg(s,v(w))+eg(d , s)=eg(ds,v(w))(xsdgd(x)2eg(s,s))+(2r|s|xsdgd(x))=eg(ds,v(w))2xsdgd(x)+2eg(s,s)+2r|s|2m2(xsdhd(x)+eg(u , s)+dgd(u))+2eg(s,s)+2r|s|=2m2xsdhd(x)2dgd(u)+2eg(s , s)+2r|s|2m2xsdhd(x)+2r|s|2r . now ( 7 ) implies 2r|d|2m2xsdhd(x)2r+2r|s|2m2(k|s|k|d|1)2r+2r|s| .
thus ( 2r2k)(|d||s|)2m2r+22k2r+2 , from which it follows that |d||s| , a contradiction . hence case 2 also
we have 2r|d|eg(ds,v(w))2xsdgd(x)+2eg(s,s)+2r|s|=eg(ds,v(w))2(xsdhd(x)+eg(u , s)+dgd(u))+2eg(s,s)+2r|s|=eg(ds,v(w))2xsdhd(x)2dgd(u)+2eg(s , s)+2r|s|2mc(w)2xsdhd(x)2r+2r|s|(since  g  is  2m - connected)(2m2)c(w)+(2r2k)|s|2r+2k|d|+4(by inequality ( 1))4m2r+(2r2k)|s|+2k|d| .
thus we have ( 2r2k)(|d||s|+1)2 m , from which it follows |d||s| . for every odd component c of w , the integer k|v(c)|+eh(v(c),s )
since k is an even integer , eh(v(c),s ) must be odd . thus eh(v(c),s)1 and xsdhd(x)qh(d , s;k ) .
hence ( 1 ) implies k|s|k|d|+2 , from which it follows that |s||d|+1 , a contradiction .
next assume condition ( ii ) of the hypothesis ; that is , k3 is odd and 2m > r . now
we obtain ( 8)|d||s|mrq11rxsdhd(x ) . by ( 1 ) , we have ( 9)|d||s|1k(qxsdhd(x)2 ) , and qk+2 since |d|>|s| . by ( 8) and ( 9 )
 in the following discussion , let  be the graph obtained from the complete graph k2r+1 by deleting a matching of size m. the bounds are sharp .
let g1 be the bipartite graph with bipartition ( u , w ) obtained by deleting a matching of size m from k2r,2r .
let g be the 2r - regular graph obtained by matching the 2 m vertices of degree 2r1 in  to 2 m vertices of degree 2r1 in g1 . clearly , g is 2m - edge - connected .
now we show that gu contains no m-factor for all uuw . without loss of generality , suppose that uu
note that qg(d , s;m)=1 if mm ( mod 2 ) and qg(d , s;m)=0 if mm ( mod 2 ) .
let h be the 2r - regular graph obtained by matching the 2r2 vertices of degree 2r1 in each of 2r1 disjoint copies of  to the vertex set s of mr1 .
since co(hv(mr1))=2r1>|v(mr1)v|=2r3 for all vv(mr1 ) , by theorem  1.2 , gv contains no 1-factor for all vv(mr1 ) .
let r1 denote the complete bipartite graph k2r,2r1 with bipartition ( u , w ) , where |u|=2r and |w|=2r1 .
take two copies of . match 4 m vertices of degree 2r1 of two copies of  to 4 m vertices of degree 2r1 of k2r,2r1 , and then add a matching of size r2 m to the rest vertices of degree 2r1 of k2r,2r1 .
this produces a 2r - regular , 2m - edge - connected graph r. let uu and r=ru .
since k is odd , qr(d , s;k)=2 and hence we have k|d|k|s|+xsdrd(x)qg(d , s;k)=2<0 . by theorem  1.3
 let k , m , and r be three integers such that 2kmr . 
 let g be a 2r - regular , 2m - edge - connected graph of odd order . 
 we obtain some sufficient conditions for gv to contain a k - factor for all vv(g ) . 
Introduction
The proof of 