On factors with all degrees odd (Q1063044)

Finite undirected graphs are considered. \(A\{\) 1,3,...,2n-1\(\}\)-factor of a graph G is a spanning subgraph of G in which the degree of every vertex belongs to the set \(\{\) 1,3,...,2n-1\(\}\), where n is a natural. Main results of paper: Theorem 1. Let G be a tree of even order and n a positive integer. Then G has a \(\{\) 1,3,...,2n-1\(\}\)-factor if and only if the number of odd components of G-v is at most 2n-1 for every vertex of G. Theorem 2. Let G be a graph and n a positive integer. Then G has a \(\{\) 1,3,...,2n-1\(\}\)-factor if and only if for every subset S of the vertex-set of G the number of odd components of G-S is at least (2n- 1)\(| S|\). These theorems extend some well-known results (for example Tutte's 1-Factor Theorem).