Regular graph

Regular graph --- регулярный граф, однородный граф.

[math]\displaystyle{ G }[/math] is a regular graph of degree [math]\displaystyle{ k }[/math], if every vertex is incident with [math]\displaystyle{ k }[/math] edges (i.e., every vertex has the degree equal to [math]\displaystyle{ k }[/math]).

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 [math]\displaystyle{ (r,s) }[/math]-regular, if the degree of each vertex is either [math]\displaystyle{ r }[/math] or [math]\displaystyle{ s }[/math].