# Regular graph

In graph theory , a graph is called regular if all of its nodes have the same number of neighbors, i.e. have the same degree . In the case of a regular directed graph , the stronger condition must apply that all nodes have the same degree of entry and exit . A regular graph with nodes of degree k is called k-regular or regular graph of degree k .

Regular graphs with a degree of at most 2 are easy to classify: a 0-regular graph consists of disconnected nodes, a 1-regular graph consists of disconnected edges, and a 2-regular graph consists of disconnected circles .

A 3-regular graph is also called a cubic graph .

A strongly regular graph is a regular graph in which every 2 neighboring nodes have exactly a common neighbors , and every two non-neighboring nodes have exactly b common neighbors. The smallest regular, but not strongly regular graph is the circle graph and the circular graph with 6 nodes each.

The full graph is strongly regular for each . ${\ displaystyle K_ {m}}$ ${\ displaystyle m}$ According to a Nash-Williams theorem , every k -regular graph with vertices has a Hamilton cycle . ${\ displaystyle 2k + 1}$ ## Algebraic properties

Let A be the adjacency matrix of a graph. The graph is regular if an eigenvector of A is. The eigenvalue of this vector is synonymous with the degree of the graph. Eigenvectors with other eigenvalues ​​are orthogonal to , i.e. H. for such eigenvectors applies: . ${\ displaystyle {\ textbf {j}} = (1, \ dots, 1)}$ ${\ displaystyle {\ textbf {j}}}$ ${\ displaystyle v = (v_ {1}, \ dots, v_ {n})}$ ${\ displaystyle \ textstyle \ sum _ {i = 1} ^ {n} v_ {i} = 0}$ A regular graph of degree k is connected if and only if the eigenvalue k has the multiplicity one.

## Combinatorics

The number of connected -regular graphs increases for a given essentially faster than exponentially with the number of nodes . Obviously, if and are odd, that number is 0. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle k}$ The following table shows the numbers determined for and using a computer : ${\ displaystyle n \ leq 16}$ ${\ displaystyle k \ leq 12}$ Number of connected regular graphs
n k
3 4th 5 6th 7th 8th 9 10 11 12
4th 1 0 0 0 0 0 0 0 0 0
5 0 1 0 0 0 0 0 0 0 0
6th 2 1 1 0 0 0 0 0 0 0
7th 0 2 0 1 0 0 0 0 0 0
8th 5 6th 3 1 1 0 0 0 0 0
9 0 16 0 4th 0 1 0 0 0 0
10 19th 59 60 21st 5 1 1 0 0 0
11 0 265 0 266 0 6th 0 1 0 0
12 85 1544 7848 7849 1547 94 9 1 1 0
13 0 10778 0 367860 0 10786 0 10 0 1
14th 509 88168 3459383 21609300 21609301 3459386 88193 540 13 1
15th 0 805491 0 1470293675 0 1470293676 0 805579 0 17th
16 4060 8037418 2585136675 113314233808 733351105934 733351105935 113314233813 2585136741 8037796 4207