Regular graph

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 vertex are equal to each other. A regular graph with vertices of degree formula_1 is called a formula_1‑regular graph or regular graph of degree formula_1. Also, from the handshaking lemma, a regular graph contains even number vertices with odd degree.
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.
A 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 "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 formula_4 is strongly regular for any formula_5.
A theorem by Nash-Williams says that every formula_1‑regular graph on 2k</var > + 1</span > vertices has a Hamiltonian cycle.
Existence.
It is well known that the necessary and sufficient conditions for a formula_1 regular graph of order formula_8 to exist are that formula_9 and that formula_10 is even.
Proof: As we know 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 formula_11 and order here is formula_12. So formula_13. This is the minimum formula_8 for a particular formula_1. Also note that if any regular graph has order formula_8 then number of edges are formula_17 so formula_18 has to be even.
In such case it is easy to construct regular graphs by considering appropriate parameters for circulant graphs.
Algebraic properties.
Let "A" be the adjacency matrix of a graph. Then the graph is regular if and only if formula_19 is an eigenvector of "A". Its eigenvalue will be the constant degree of the graph. Eigenvectors corresponding to other eigenvalues are orthogonal to formula_20, so for such eigenvectors formula_21, we have formula_22.
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 formula_23, 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 formula_24. If "G" is not bipartite, then
Generation.
Fast algorithms exist to enumerate, up to isomorphism, all regular graphs with a given degree and number of vertices.