ON GRAPH CONNECTIVITY AFTER PATH REMOVAL

In this paper we show that for any two vertices x, y of a 6-connected graph G, there exists a path between them whose removal leaves G 3-connected. This proves the case of Lovasz’s path removal conjecture (1975), where f(3) = 6. This article examines the relationship between connectivity and path removal. The following definition of connectivity is used frequently Definition 1. A graph G is k − connected if a set S of k vertices disconnects the graph into at least two components C1 and C2 and S and no set S of k − 1 vertices disconnects the graph. Definition 2. A k vertex cut in a graph G is a set of k vertices which disconnects the graph into at least two components C1 and C2. Thus any k-connected graph must contain a k-vertex cut which disconnects the graph into at least two components. By definition, the complete graph on n vertices, Kn, is n − 1-connected. In order to describe a graph in terms of sets we need the following definitions