INDECOMPOSABLE REGULAR GRAPHS AND HYPERGRAPHS

Let G be a d-regular simple graph with n vertices. Here it is proved that for d > square-root n - 1, G contains a proper regular spanning subhypergraph. The same statement is proved for multigraphs with d > (n - 1)/3. These bounds are best possible if d is odd. The main tool of the proof is a consequence of Tutte's f-factor theorem on the existence of 2-factors, due to Taskinov. Finally, disproving a conjecture of Alon and Berman, an indecomposable d-regular 3-uniform hypergraph is constructed with d greater-than-or-equal-to 2(n-6)/2.