3connected

3connected is a term most often encountered in graph theory to describe a class of graphs that are 3-vertex-connected. In addition, the string may be used as a stylized name for brands, projects, or organizations in other contexts. This article focuses on the mathematical usage, while noting that the term may appear in non-academic settings.

Definition and basic meaning

A graph G is called 3-connected if its vertex connectivity κ(G) is at least 3. Equivalently, G remains connected after removing any two vertices, and there is no set of fewer than three vertices whose removal disconnects the graph. By Menger’s theorem, this is also characterized by the existence of at least three internally disjoint paths between every pair of vertices. A 3-connected graph must have at least four vertices, and every vertex has degree at least 3.

Properties and implications

3-connected graphs are, by definition, also 2-connected and thus have no cut vertices. They exhibit a form of robust connectivity: removing up to two vertices cannot partition the graph. In planar graphs, Whitney’s theorem states that a 3-connected planar graph has a unique embedding on the sphere, up to mirror symmetry. Ear decompositions provide constructive ways to build 3-connected graphs, starting from a cycle and successively adding paths that attach at two endpoints.

Examples and applications

Completed graphs on four or more vertices, such as K4, K5, and K6, are 3-connected. More generally, complete graphs with n ≥ 4 vertices are 3-connected or stronger. Beyond pure theory, 3-connected graphs are relevant in network design for fault-tolerant communication, circuit layout, and various problems in topological graph theory.

Other uses

The term 3connected may also appear as a brand or project name in technology, design, or media, separate from the graph-theoretic concept.