2vertexconnected

2vertexconnected refers to graphs that are two-vertex-connected, also called 2-connected. A graph is 2vertexconnected if it is connected and remains connected after removing any single vertex. Equivalently, the graph has no articulation points (vertices whose removal increases the number of connected components). This property is captured by the vertex connectivity κ(G) being at least 2.

Key related concepts include Menger’s theorem, which states that in a 2vertexconnected graph there are at least two internally vertex-disjoint paths between every pair of vertices. Consequently, for any two vertices there exist two distinct ways to connect them without sharing interior vertices. The minimum degree δ(G) must be at least 2 for a graph to be 2vertexconnected, but this condition alone is not sufficient.

2vertexconnected graphs have several structural implications. They contain no bridges (edges whose removal increases the number of components), and removing any vertex cannot disconnect the graph. In a connected graph, the property is reflected in its block structure: a 2vertexconnected graph consists of a single block; if a graph has articulation points, it decomposes into multiple blocks connected at those points.

Common examples include cycle graphs Cn with n ≥ 3 and complete graphs Kn with n ≥ 3. Not all connected graphs are 2vertexconnected; for instance, two triangles that share a single vertex form a connected graph with a cut-vertex and are not 2vertexconnected.

Algorithms exist to test 2vertexconnectivity in linear time. Depth-first search algorithms identify articulation points and can determine κ(G) ≥ 2 efficiently. These algorithms underpin many practical applications in network design, reliability analysis, and graph decomposition.