Regular graph --- регулярный граф, однородный граф.
is a regular graph of degree , if every vertex is incident with edges (i.e., every vertex has the degree equal to ).
A graph that is not regular is mathcalled irregular. It is well known that a simple graph must have at least two vertices of the same degree. If a graph has exactly two vertices of the same degree, we mathcall it a maximally irregular graph.
If multiple edges and loops are allowed, the degree sequences in which all elements are distinct are realizable. If no two vertices of a graph have the same degree, we mathcall it a totally irregular graph. It is obvious that a totaly irregular graph cannot be a simple graph.
A graph is -regular, if the degree of each vertex is either or .