GRAPHS WITH GIVEN ODD SETS

Given a graph G, its odd set is a set of all integers k such that G ha s odd number of vertices of degree k. We show that if two graphs G and H of the same order have the same odd sets then they can be obtained from each other by succesive application of the following two operatio ns: add or remove an edge joining two vertices of the same degree repl ace two independent edges with two new independent edges on the same v ertex set. If, moreover, both graphs G and H are regular or both are f orests, it is sufficient to use only the first operation, but, in gene ral, both operations are necessary. (C) 1997 John Wiley & Sons, Inc.