View source for Regular graph

{{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 (discrete mathematics)|graph]] where each [[Vertex (graph theory)|vertex]] has the same number of neighbors; i.e. every vertex has the same [[Degree (graph theory)|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 graphs|disjoint union]] of [[cycle (graph theory)|cycle]]s 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 [[Crispin St. J. A. Nash-Williams|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 [[eigenvalue]]s 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 [[Glossary of graph theory#order|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 graph|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]]
[[Category:Regular graphs|*]]