Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Regular graph

Graph where each vertex has the same number of neighbors

Wikipedia contributorsAdapted for Fathomly · View authors
3 min read
Source updated September 1, 2025

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each internal vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k.

01Special cases

Regular graphs of degree at most 2 are easy to classify: a 0-regular graph consists of disconnected vertices, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of a disjoint union of cycles and infinite chains.

In analogy with the terminology for polynomials of low degrees, a 3-regular or 4-regular graph often is called a cubic graph or a quartic graph, respectively. Similarly, it is possible to denote k-regular graphs with k=5,6,7,8,\ldots as quintic, sextic, septic, octic, et cetera.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number l of neighbors in common, and every non-adjacent pair of vertices has the same number n of neighbors in common. The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices.

The complete graph Km is strongly regular for any m.

02Properties

By the degree sum formula, a k-regular graph with n vertices has {\frac {nk}{2}} edges. In particular, at least one of the order n and the degree k must be an even number.

A theorem by Nash-Williams says that every k‑regular graph on 2k + 1 vertices has a Hamiltonian cycle.

Let A be the adjacency matrix of a graph. Then the graph is regular if and only if {\textbf {j}}=(1,\dots ,1) is an eigenvector of A. Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to {\textbf {j}}, so for such eigenvectors v=(v_{1},\dots ,v_{n}), we have \sum _{i=1}^{n}v_{i}=0.

A regular graph of degree k is connected if and only if the eigenvalue k has multiplicity one. The "only if" direction is a consequence of the Perron-Frobenius theorem.

There is also a criterion for regular and connected graphs : a graph is connected and regular if and only if the matrix of ones J, with J_{ij}=1, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of A).

Let G be a k-regular graph with diameter D and eigenvalues of adjacency matrix k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}. If G is not bipartite, then

D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.

03Existence

There exists a k-regular graph of order n if and only if the natural numbers n and k satisfy the inequality n\geq k+1 and that nk is even.

Proof: If a graph with n vertices is k-regular, then the degree k of any vertex v cannot exceed the number n-1 of vertices different from v, and indeed at least one of n and k must be even, whence so is their product.

Conversely, if n and k are two natural numbers satisfying both the inequality and the parity condition, then indeed there is a k-regular circulant graph C_{n}^{s_{1},\ldots ,s_{r}} of order n (where the s_{i} denote the minimal `jumps' such that vertices with indices differing by an s_{i} are adjacent). If in addition k is even, then k=2r, and a possible choice is (s_{1},\ldots ,s_{r})=(1,2,\ldots ,r). Else k is odd, whence n must be even, say with n=2m, and then k=2r-1 and the `jumps' may be chosen as (s_{1},\ldots ,s_{r})=(1,2,\ldots ,r-1,m).

If n=k+1, then this circulant graph is complete.

04Generation

Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.

Watch videos about Regular graphExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Regular graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Random regular graph

A random r-regular graph is a graph selected from G n , r {\displaystyle {\mathcal {G}}_{n,r}} , which denotes the probability space of all r-regular graphs on n {\displaystyle n} vertices, where 3 ≤ r < n {\displaystyle 3\leq r<n} and n r {\displaystyle nr} is even. It is therefore a particular kind of random graph, but the regularity restriction significantly alters the properties that will hold, since most graphs are not regular.

Strongly regular graph

In graph theory, a strongly regular graph is a regular graph G = (V, E) with v vertices and degree k such that for some given integers λ , μ ≥ 0 {\displaystyle \lambda ,\mu \geq 0} every two adjacent vertices have λ common neighbours, and every two non-adjacent vertices have μ common neighbours. Such a strongly regular graph is denoted by srg(v, k, λ, μ).

Moore graph

In graph theory, a Moore graph is a regular graph whose girth is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is d and its diameter is k, its girth must equal 2k + 1.