Cycles and Connectivity in Graphs

Abstract

In this note, G will denote a finite undirected graph without multiple edges, and V = V(G) will denote its vertex set. The largest integer n for which G is n-vertex connected is the vertex-connectivity of G and will be denoted by λ = λ(G). One defines ζ to be the largest integer z not exceeding |V| such that for any set U ⊂ V with |U| = z, there is a cycle in G which contains U. The symbol i(U) will denote the component index of U. As a standard reference for this and other terminology, the authors recommend O. Ore (3).