{{short description|Graph where each vertex has the same number of neighbors}} {{refimprove|date=November 2022}} {{Graph families defined by their automorphisms}} 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.<ref> {{Cite book | last = Chen | first = Wai-Kai | title = Graph Theory and its Engineering Applications | publisher = World Scientific | year = 1997 | pages = [https://archive.org/details/graphtheoryitsen00chen/page/29 29] | isbn = 978-981-02-1859-1 | url-access = registration | url = https://archive.org/details/graphtheoryitsen00chen/page/29 }}</ref> A regular graph with vertices of degree {{mvar|k}} is called a '''{{nowrap|{{mvar|k}}‑regular}} graph''' or regular graph of degree {{mvar|k}}.

{{tocleft}} ==Special cases== Regular graphs of degree at most 2 are easy to classify: a {{nowrap|0-regular}} graph consists of disconnected vertices, a {{nowrap|1-regular}} graph consists of disconnected edges, and a {{nowrap|2-regular}} graph consists of a disjoint union of cycles and infinite chains.

In analogy with the terminology for polynomials of low degrees, a {{nowrap|3-regular}} or {{nowrap|4-regular}} graph often is called a cubic graph or a quartic graph, respectively. Similarly, it is possible to denote ''k''-regular graphs with <math>k=5,6,7,8,\ldots</math> as quintic, sextic, septic, octic, ''et&nbsp;cetera''.

A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number {{mvar|l}} of neighbors in common, and every non-adjacent pair of vertices has the same number {{mvar|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 {{mvar|K{{sub|m}}}} is strongly regular for any {{mvar|m}}.

<gallery class="skin-invert-image"> Image:0-regular_graph.svg|0-regular graph Image:1-regular_graph.svg|1-regular graph Image:2-regular_graph.svg|2-regular graph Image:3-regular_graph.svg|3-regular graph </gallery>

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

A theorem by Nash-Williams says that every {{nowrap|{{mvar|k}}‑regular}} graph on {{math|2''k'' + 1}} vertices has a Hamiltonian cycle.

Let ''A'' be the adjacency matrix of a graph. Then the graph is regular if and only if <math>\textbf{j}=(1, \dots ,1)</math> is an eigenvector of ''A''.<ref name="Cvetkovic">Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to <math>\textbf{j}</math>, so for such eigenvectors <math>v=(v_1,\dots,v_n)</math>, we have <math>\sum_{i=1}^n v_i = 0</math>.

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.<ref name="Cvetkovic"/>

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 <math>J_{ij}=1</math>, is in the adjacency algebra of the graph (meaning it is a linear combination of powers of ''A'').<ref>{{citation | last = Curtin | first = Brian | doi = 10.1007/s10623-004-4857-4 | issue = 2–3 | journal = Designs, Codes and Cryptography | mr = 2128333 | pages = 241–248 | title = Algebraic characterizations of graph regularity conditions | volume = 34 | year = 2005}}.</ref>

Let ''G'' be a ''k''-regular graph with diameter ''D'' and eigenvalues of adjacency matrix <math>k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math>. If ''G'' is not bipartite, then

: <math>D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. </math><ref>{{Cite journal| doi = 10.1006/aima.1994.1052| issn = 0001-8708| volume = 106| issue = 1| pages = 122–148| last = Quenell| first = G.| title = Spectral Diameter Estimates for <i>k</i>-Regular Graphs| journal = Advances in Mathematics| access-date = 2025-04-10| date = 1994-06-01| url = https://www.sciencedirect.com/science/article/pii/S0001870884710528| url-access = subscription}}[https://www.sciencedirect.com/science/article/pii/S0001870884710528]</ref>

== Existence ==

There exists a <math>k</math>-regular graph of order <math>n</math> if and only if the natural numbers {{mvar|n}} and {{mvar|k}} satisfy the inequality <math> n \geq k+1 </math> and that <math> nk </math> is even.

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

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

If <math>n=k+1</math>, then this circulant graph is complete.

== Generation == Fast algorithms exist to generate, up to isomorphism, all regular graphs with a given degree and number of vertices.<ref>{{cite journal| last=Meringer | first=Markus | year=1999 | title=Fast generation of regular graphs and construction of cages | journal=Journal of Graph Theory | volume=30 | issue=2 | pages=137&ndash;146 | doi= 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G| url=http://www.mathe2.uni-bayreuth.de/markus/pdf/pub/FastGenRegGraphJGT.pdf}}</ref>

== See also == * Random regular graph * Strongly regular graph * Moore graph * Cage graph * Highly irregular graph

== References == {{reflist}}

== External links == * {{MathWorld|urlname=RegularGraph|title=Regular Graph}} * {{MathWorld|urlname=StronglyRegularGraph|title=Strongly Regular Graph}} * [http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html GenReg] software and data by Markus Meringer. * {{Citation | last=Nash-Williams | first=Crispin |author-link = Crispin St. J. A. Nash-Williams | title=Valency Sequences which force graphs to have Hamiltonian Circuits | series=University of Waterloo Research Report | publisher=University of Waterloo | place=Waterloo, Ontario | year=1969 }}

{{DEFAULTSORT:Regular Graph}} Category:Graph families *