A Property on Edge-disjoint Spanning Trees

LetGbe a simple graph withnvertices and letGcdenote the complement ofG. Letω(G)denote the number of components ofGandG(E) the spanning subgraph ofGwith edge setE. Suppose that |E|=k(|V(G) |-1). Consider the partition Π=〈X1, X2, . . . , Xk〉 ofE(G) such that |Xi|=n-1 (1≤i≤k). Defineϵ( Π)=Σki=1 ω(G(Xi))-kandϵ(G)=min ϵ(Π),where the minimum is taken over all such partitions. In [Europ. J. Combin.7(1986), 263-270], Payan conjectures that ifϵ(G)>0, then there exist edgese∈E(G) ande′∈E(Gc)such thatϵ(G-e+e′)<ϵ(G). This conjecture will be proved in this note.