3regular

In graph theory, a 3-regular graph (often written as 3-regular, and also called cubic or trivalent) is a graph in which every vertex has degree exactly 3. More generally, a k-regular graph is a graph where every vertex has degree k. A 3-regular graph may be simple (no loops or multiple edges) or may include multiple edges or loops if not restricted, but the standard study often focuses on finite simple graphs.

For a finite simple 3-regular graph with n vertices and m edges, the handshaking lemma gives m = 3n/2. Consequently, n must be even. Such graphs may be connected or decomposed into several components. The smallest connected 3-regular graph is the complete graph K4.

Common examples include K4, the complete bipartite graph K3,3 (the utility graph), the Petersen graph, and the Heawood graph. These examples illustrate the diversity of 3-regular graphs in terms of planarity, symmetry, and girth.

A notable property is that a 3-regular graph is called cubic. They can be connected or disconnected, planar or nonplanar, and may contain short cycles such as triangles. When a cubic graph is bridgeless (has no cut-edge), Petersen's theorem guarantees the existence of a perfect matching. This implies that the edge set can be partitioned into a perfect matching and a 2-regular subgraph, i.e., a collection of disjoint cycles.

Applications of 3-regular graphs appear in chemistry as models of trivalent carbon frameworks, in network design, and in various areas of graph theory, including studies of Hamiltonicity, colorings, and matching theory. Cubic graphs thus occupy a central place in the theory of regular graphs.