Editing Regular graph (section)

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