threeconnected

Threeconnected is a term used in graph theory to describe graphs that are three-vertex-connected. A graph G is threeconnected if it is connected and remains connected after the removal of any two vertices. Equivalently, G has vertex connectivity κ(G) = 3, meaning that at least three vertices must be removed to disconnect the graph or reduce it to a single vertex. By Menger's theorem, between any pair of vertices there exist three internally disjoint paths, which provides an alternative way to understand the condition.

Threeconnected graphs are, in particular, 2-connected and hence cannot be separated by a single vertex; they have no separating pair of vertices. This property yields several consequences: for planar graphs, Whitney's theorem states that a planar graph that is 3-connected has a unique embedding on the sphere up to a homeomorphism; Steinitz's theorem further characterizes the planar 3-connected graphs as exactly the skeletons of convex polyhedra.

Common examples include the complete graph on four vertices, K4, which is minimally 3-connected, and many polyhedral graphs that arise as faces of convex solids. Some graphs are 4-connected or higher, and thus also threeconnected by implication.

In practice, recognizing and working with threeconnected graphs is important in network design and computational geometry, and there are algorithms to test 3-connectivity and to decompose graphs into triconnected components.

See also: vertex connectivity, Menger's theorem, 2-connected graph, Steinitz's theorem, polyhedral graph.