Editing 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.

A {{nowrap|3-regular}} graph is known as a [[cubic graph]].

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>

== Existence ==

The necessary and sufficient conditions for a <math>k</math>-regular graph of [[Glossary of graph theory#order|order]] <math>n</math> to exist are that <math> n \geq k+1 </math> and that <math> nk </math> is even.

Proof: A [[complete graph]] has every pair of distinct vertices connected to each other by a unique edge. So edges are maximum in complete graph and number of edges are <math>\binom{n}{2} = \dfrac{n(n-1)}{2}</math> and degree here is <math>n-1</math>. So <math>k=n-1,n=k+1</math>. This is the minimum <math>n</math> for a particular <math>k</math>. Also note that if any regular graph has order <math>n</math> then number of edges are <math>\dfrac{nk}{2}</math> so <math>nk</math> has to be even.
In such case it is easy to construct regular graphs by considering appropriate parameters for [[circulant graph]]s.

==Properties==
From the [[handshaking lemma]], a {{mvar|k}}-regular graph with odd {{mvar|k}} has an even number of vertices.

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}}[https://www.sciencedirect.com/science/article/pii/S0001870884710528]</ref>

== 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|*]]