On the maximal number of disjoint circuits of a graph
P. Erdős, L. Pósa
Abstract
Throughout this paper Gg " will denote a graph with n vertices and k edges where circuits consisting of two edges and loops (i. e. circuits of one edge) are not permitted and G' " will denote a graph of n vertices and k edges where loops and circuits with two edges are permitted. v(G) (respectively v(G)) will denote the number of edges of G (respectively G). If x,, x "..., x,, are some of the vertices of G, then (G-x,-...-x k) will denote the graph which we obtain from G by omitting the vertices x,,..., x k and all the edges incident to them. By G(x,,..., x k) we denote the subgraph of G spanned by the vertices x,,..., xk. The valency of a vertex x- v (x)- will denote the number of edges incident to it. (A loop is counted doubly.) The edge connecting x, and x, will be denoted by [x,, x,], edges will sometimes be denoted by e,, ez,.... (x,, x,,...xk) will denote the circuit having the edges [x,, x,],..., [xk _,,.vk], [x k x,]. A set of edges is called independent if no two of them have a common vertex. A set of circuits will be called independent if no two of them have a common vertex. They will be called weakly independent if no two of them have a common edge. In a previous paper ERDŐS and GALLAI [l] proved that every (l) G,+i where 1=max