Regular graph
In graph theory, a regular graph is a graph in which every vertex has the same degree, meaning each vertex is incident to the same number of edges.[1] This common degree is denoted by k, and the graph is then called a k-regular graph.[2] The number of edges in a k-regular graph with n vertices is \frac{1}{2}kn, as derived from the handshaking lemma applied uniformly across all vertices.[1] For such a graph to exist, $0 \leq k \leq n-1 must hold, and kn must be even, ensuring the total degree sum is even and compatible with the lemma.[2] Their uniform degree structure facilitates their use in studying structural properties like connectivity, matchings, and colorings; for instance, every k-regular bipartite graph with k > 0 has a perfect matching by Hall's marriage theorem.[1] Common examples include the complete graph K_n, which is (n-1)-regular, and the empty graph on n vertices, which is 0-regular.[1] The cycle graph C_n for n \geq 3 is 2-regular, and the complete bipartite graph K_{m,m} is m-regular.[2] Regular graphs are foundational in areas such as random graph theory, where models of random d-regular graphs analyze properties like Hamilton cycles and spanning subgraphs with high probability.[3] They also appear in applications to computer science for modeling symmetric networks and in combinatorial designs for constructing balanced structures.[3]Definition and Fundamentals
Definition
A regular graph is an undirected graph in which every vertex has the same degree k, and such a graph is denoted as k-regular.[4][5] This uniformity of degree distinguishes regular graphs from irregular graphs, where vertices may have varying degrees.[4] The concept applies to both simple graphs, which contain no loops or multiple edges between the same pair of vertices, and multigraphs, which permit loops and multiple edges; however, definitions in graph theory often assume simple graphs unless specified otherwise.[5] The term "regular graph" was introduced by Julius Petersen in his 1879 paper "Die Theorie der regulären Graphs".[6] The concept was further developed in the early 20th century, notably through the work of Hungarian mathematician Dénes König, who employed it in his 1916 proofs on bipartite regular graphs and formalized it in his seminal 1936 textbook, Theory of Finite and Infinite Graphs, the first comprehensive book on the subject.[7][8] A representative example of a k-regular graph is the complete graph K_{k+1}, which has k+1 vertices where each connects to every other, achieving degree k and representing the smallest such graph on that number of vertices.[9] While regular graphs can be infinite, with every vertex maintaining degree k across an unbounded structure, the focus in classical graph theory remains on finite regular graphs.[5]Basic Terminology
A regular graph G is denoted by G = (V, E), where V is the vertex set and E is the edge set, with every vertex v \in V having degree \deg(v) = k, for some fixed integer k \geq 0.[5] Such a graph is called a k-regular graph on n vertices, or simply G_n^k.[5] The order of a regular graph G is the number of vertices n = |V|.[5] The size of G is the number of edges m = |E|; for a k-regular simple graph, the handshaking lemma implies m = nk/2.[5] The girth of G is the length of its shortest cycle, or infinite if G is acyclic.[5] The diameter of a connected graph G is the maximum distance between any two vertices.[5] A strongly regular graph is a regular graph with additional constraints on the number of common neighbors for adjacent and non-adjacent vertex pairs.[10] A biregular graph is a bipartite graph in which all vertices in one part have degree r and all in the other have degree s.[11] Throughout this article, regular graphs are assumed to be undirected and simple unless otherwise specified; in multigraphs, loops contribute 2 to the degree of their incident vertex.[5]Properties
Combinatorial Properties
A fundamental combinatorial property of regular graphs follows from the handshaking lemma. In a k-regular graph G with n vertices, the sum of all vertex degrees is nk, which equals twice the number of edges m, yielding m = nk/2. Consequently, nk must be even for m to be an integer, implying that either n or k is even.[12] The uniformity of degrees in regular graphs also implies strong connectivity guarantees. Moreover, such graphs are k-edge-connected, requiring the removal of at least k edges to disconnect them.[13] Regular graphs exhibit notable isoperimetric properties, particularly in bounding edge cuts and expansion. The isoperimetric number h(G) of a k-regular graph G on n vertices is defined as h(G) = \min_{U \subseteq V(G), \, 0 < |U| \leq n/2} \frac{|E(U, V(G) \setminus U)|}{|U|}, measuring the minimum edge expansion relative to subset size.[14] Such bounds are central to expander graphs, where high h(G) ensures strong connectivity despite low density.[14] Counting walks in regular graphs leverages their degree homogeneity combinatorially. In a k-regular graph G with n vertices, the total number of walks of length \ell (allowing vertex and edge revisits) is exactly n k^\ell, as each of the n starting vertices admits k choices at each of the \ell steps.[15] The number of walks of length \ell from a fixed vertex u to v is given by the (u,v)-entry of the \ellth power of the adjacency matrix A(G), denoted (A^\ell)_{uv}, and the total closed walks of length \ell equals \operatorname{trace}(A^\ell). Eigenvalues influence these counts, but the combinatorial total n k^\ell holds independently.[15] Eulerian properties provide another key combinatorial insight. A connected k-regular graph G admits an Eulerian circuit—a closed trail traversing each edge exactly once—if and only if k is even, since all degrees are then even. For odd k, no such circuit exists in simple graphs, but allowing multiple edges (as in multigraphs) permits Eulerian circuits under connectivity. This follows from Euler's theorem, which equates Eulerian circuits with even degrees in connected graphs.Algebraic Properties
The adjacency matrix A of a k-regular graph on n vertices is a symmetric n \times n matrix with zero diagonal entries and exactly k ones in each row and column, reflecting the regularity of the graph. As a result, the all-ones vector serves as an eigenvector corresponding to the largest eigenvalue k. For connected k-regular graphs, this eigenvalue has algebraic multiplicity one.[16] The spectral gap of a connected k-regular graph is given by k - \lambda_2, where \lambda_2 is the second-largest eigenvalue of A. This gap quantifies the graph's expansion properties, providing upper bounds on the Cheeger constant, and also determines the mixing time of the associated random walk, which is O\left( \frac{\log n}{k - \lambda_2} \right). Larger gaps correspond to stronger expanders with faster convergence to the stationary distribution.[17] For a k-regular graph, the (unnormalized) Laplacian matrix is L = kI - A, where I is the identity matrix. The eigenvalues of L are \mu_i = k - \lambda_i for i = 1, \dots, n, lying in the interval [0, 2k], with \mu_1 = 0 having multiplicity one if the graph is connected. The second-smallest eigenvalue \mu_2 (algebraic connectivity) further bounds expansion and connectivity.[18] The trace of the m-th power of the adjacency matrix, \operatorname{Tr}(A^m) = \sum_{i=1}^n \lambda_i^m, equals the total number of closed walks of length m in the graph. This relation links the spectrum to combinatorial walk counts, enabling spectral methods to analyze walk distributions in regular graphs. A k-regular graph is Ramanujan if every non-trivial eigenvalue \lambda_i (for i \geq 2) satisfies |\lambda_i| \leq 2\sqrt{k-1}, achieving the optimal spectral gap conjectured by Alon and proven nearly tight by Friedman for random k-regular graphs on sufficiently large n, where \lambda_2 \leq 2\sqrt{k-1} + o(1) with high probability.Special Cases
Low-Degree Regular Graphs
A 0-regular graph consists solely of isolated vertices with no edges connecting them, forming what is known as the empty graph on a given number of vertices.[4] This structure is the simplest case of a regular graph, where every vertex has degree zero, and it exists for any finite number of vertices. A 1-regular graph is a disjoint union of edges, where each component is a single edge connecting exactly two vertices, and every vertex has degree one.[4] Such graphs exist only when the total number of vertices is even, as the handshaking lemma requires the sum of degrees to be even, pairing all vertices perfectly in a matching. This configuration is equivalent to a perfect matching spanning the vertex set, with no isolated vertices or larger components.[19] In contrast, a 2-regular graph comprises one or more disjoint cycles, where every vertex has exactly two neighbors, forming closed loops without branches.[4] These graphs exist for any number of vertices greater than or equal to 3, by partitioning the vertices into cycles of lengths at least 3. When connected, a 2-regular graph is precisely the cycle graph C_n for n \geq 3, a fundamental structure in graph theory that models circular arrangements.[20] 3-regular graphs, also called cubic graphs, are more complex, with each vertex incident to exactly three edges, requiring an even number of vertices for existence by the handshaking lemma. A seminal result is Petersen's theorem, which states that every bridgeless 3-regular graph contains a perfect matching.[21] This theorem, originally proved in 1891, guarantees a 1-factor in such graphs without bridges, highlighting their decomposability properties.[22] However, not all 3-regular graphs are Hamiltonian; the Petersen graph on 10 vertices serves as the smallest counterexample, being non-Hamiltonian despite its symmetry and connectivity.[23] For planarity in 3-regular graphs, Euler's formula imposes strict bounds related to girth, the length of the shortest cycle. In a simple planar graph with girth g, the number of edges e satisfies e \leq \frac{g}{g-2}(v-2).[24] For 3-regular graphs, where e = \frac{3v}{2}, this implies that planar realizations cannot have girth 6 or higher, as substituting g=6 yields \frac{3v}{2} \leq \frac{3}{2}(v-2), simplifying to a contradiction $0 \leq -3. Graphs with girth 5, such as the dodecahedral graph on 20 vertices, achieve the bound near equality and are planar, while those with girth 4 may be non-planar, as exemplified by the utility graph K_{3,3}, a 3-regular bipartite graph on 6 vertices that contains no odd cycles but violates planarity by Kuratowski's theorem.Highly Symmetric Regular Graphs
Complete graphs K_n are the paradigmatic example of highly symmetric regular graphs, being (n-1)-regular on n vertices where every pair of distinct vertices is adjacent.[25] These graphs achieve the maximum possible degree for a simple graph on n vertices, making them uniquely maximal among regular graphs of their order.[26] Their vertex-transitivity and edge-transitivity underscore their extreme symmetry, with the automorphism group isomorphic to the symmetric group S_n. Cycle graphs C_n provide a foundational instance of 2-regular symmetric graphs, consisting of n vertices connected in a single cycle, which is inherently Hamiltonian as the graph itself forms a spanning cycle.[27] For n \geq 3, C_n is vertex-transitive and edge-transitive, serving as a basic building block for more complex symmetric structures due to its uniform degree and cyclic symmetry.[28] Cage graphs represent extremal regular graphs achieving the minimal order for a given degree k and girth g, defined as the smallest k-regular graph with no cycles shorter than g.[29] The Petersen graph exemplifies this as the unique (3,5)-cage, a 3-regular graph on 10 vertices with girth 5, renowned for its symmetry and role as a Moore graph of diameter 2.[30] Strongly regular graphs form a broad class of highly symmetric regular graphs characterized by parameters (n, k, \lambda, \mu), where the graph has n vertices, is k-regular, every pair of adjacent vertices shares \lambda common neighbors, and every pair of non-adjacent vertices shares \mu common neighbors.[31] These parameters enforce a refined intersection property that enhances symmetry, often leading to distance-regularity. The Hoffman-Singleton graph illustrates this as the unique strongly regular graph with parameters (50, 7, 0, 1), a 7-regular graph on 50 vertices that is also a (7,5)-cage and Moore graph of diameter 2.[32] Moore graphs, which attain the Moore bound for the maximum number of vertices in a k-regular graph of diameter 2, are among the most symmetric regular graphs, coinciding with cages for girth 5 in known cases. Known examples include the Petersen graph for k=3, the Hoffman-Singleton graph for k=7, and the cycle graph C_5 for k=2; a possible 57-regular Moore graph on 3250 vertices remains an open question, with its existence undecided despite extensive scrutiny.[33]Existence and Constructions
Existence Conditions
A fundamental necessary condition for the existence of a k-regular graph on n vertices is that nk must be even, as the sum of degrees in any graph is twice the number of edges by the handshaking lemma.[34] This parity requirement follows directly from the fact that the total degree sum nk equals $2|E|, where |E|is the edge count, and thus must be even. Whennkis odd—which occurs precisely when bothkandn$ are odd—no such graph can exist, as it would violate this basic combinatorial constraint.[35] For sufficient conditions, a k-regular simple graph on n vertices exists whenever $0 \leq k < n, nk is even, and n \geq k+1 for k > 0. This holds for the complete graph when k = n-1, disjoint edges when k=1 (requiring n even), and more generally for intermediate degrees via inductive constructions or random methods. Specifically, for connected k-regular graphs with k \geq 2 and n \geq k+1, existence is guaranteed if nk is even; if nk is odd, a connected nearly k-regular graph (with degrees k or k-1) exists instead.[36] Non-existence cases beyond the parity condition include the impossibility of a k-regular bipartite graph on an odd number of vertices for k > 0, as the partite sets must be of equal size to balance the degrees, requiring even n. Additionally, bipartite regular graphs cannot have odd girth, since they contain no odd cycles by definition. For k=2, while 2-regular graphs (disjoint cycles) exist on odd n via an odd cycle, connected 2-regular bipartite graphs require even n for the same bipartition reason. The Erdős–Ginzburg–Ziv theorem, which states that any sequence of $2m-1 integers contains a subsequence of m elements summing to a multiple of m, has implications for graph decompositions involving regular subgraphs. It aids in proving the existence of regular factors or cycle decompositions in certain dense or regular host graphs, such as ensuring zero-sum properties in edge labelings that correspond to balanced substructures.[37] Petersen's theorem provides a key existence result for 3-regular (cubic) graphs: every bridgeless 3-regular graph on an even number of vertices contains a perfect matching (1-factor). This guarantees the decomposability of such graphs into edge-disjoint matchings under the bridgeless condition, with n \geq 4 and n even for basic existence.[38] Asymptotically, the configuration model ensures the existence of k-regular simple graphs for fixed k \geq 3 and large n with nk even. In this model, pairing nk stubs randomly yields a multigraph, which is simple (no loops or multiple edges) with probability approaching 1 as n \to \infty, thus confirming existence via positive probability.[39]Construction Methods
One prominent method for constructing regular graphs is the configuration model, introduced by Bollobás in 1980. This approach generates a random k-regular multigraph on n vertices (where nk is even) by creating nk stubs (half-edges), one for each endpoint of the k edges incident to each vertex, and then performing a random perfect matching on these stubs to form edges. The resulting multigraph may contain self-loops and multiple edges between the same pair of vertices; to obtain a simple graph, these can be resolved by rejection sampling or conditioning on the absence of such features, though the probability of multiples decreases as k grows relative to n.[40] Another constructive technique adapts the Havel-Hakimi algorithm, originally developed for realizing arbitrary graphical degree sequences, to the uniform case of regular degrees. For a k-regular graph on n vertices, the algorithm iteratively connects the highest-degree remaining vertex to the k highest-degree vertices in the residual sequence, subtracts one from their degrees, removes the connected vertex, and repeats until the sequence is exhausted or a contradiction arises; since the regular sequence is graphical under the evenness condition, this yields a simple k-regular graph. This method is deterministic and guarantees connectivity if started appropriately, though it may produce specific realizations rather than uniform random ones. Cayley graphs provide an explicit algebraic construction of regular graphs, defined on the elements of a group G with a symmetric generating set S \subseteq G excluding the identity, where vertices are group elements and edges connect g to gs for each s \in S. The resulting graph is |S|-regular and vertex-transitive. A canonical example is the n-dimensional hypercube, which is the Cayley graph of the elementary abelian group (\mathbb{Z}/2\mathbb{Z})^n generated by the standard basis vectors, yielding an n-regular graph on $2^n vertices with high symmetry and applications in parallel computing. The switching method, developed by McKay and Wormald, starts from an initial k-regular multigraph and iteratively applies local switches to eliminate multiple edges and loops while preserving degrees. Specifically, for non-adjacent edges \{a,b\} and \{c,d\} forming a multiple or loop, replace them with \{a,c\} and \{b,d\} (or \{a,d\} and \{b,c\}) if the new edges do not already exist, repeating until a simple graph is obtained; this process is Markovian and can be tuned for uniform sampling over isomorphism classes. It is particularly efficient for moderate k and n, enabling rapid generation of random regular graphs.[41] In practice, software libraries facilitate these constructions. The Python package NetworkX implements the configuration model via itsrandom_regular_graph function to generate random k-regular simple graphs on n vertices, handling multiplicity resolution internally. Similarly, the nauty suite's geng tool can enumerate or sample all non-isomorphic k-regular graphs up to small n (e.g., n \leq 32 for k=3), using canonical labeling for efficiency.[42][43]